[Java] 1959 달팽이3

문제

M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.

ㅇ	 	 
 	 	 
 	 	 
 	 	 
 	 	 
위의 그림은 M=5, N=3의 예이다.
이제 표의 왼쪽 위 칸(○)에서 시작하여, 오른쪽으로 선을 그려 나간다. 
표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 
시계방향으로 선을 꺾어서 그려나간다.

ㅇ	→	↘
↗	↘	↓
↑	↓	↓
↑	끝	↓
↖	←	↙
위의 표는 선을 그려 나간 모양을 나타낸 것이다. 
선이 꺾어진 부분은 대각선으로 나타내었다.  
표의 모든 칸이 채워질 때까지 선을 몇 번 꺾게 될까? 또, 어디에서 끝나게 될까?

입력
첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2 ≤ M, N ≤ 2,100,000,000)

출력
첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다. 
둘째 줄에 끝나는 점의 좌표를 출력한다. 
왼쪽 위 칸의 좌표를 (1, 1), 오른쪽 아래 칸의 좌표를 (M, N)이라고 하자.

문제 풀이

M과 N의 크기가 21억으로 매우 크기 때문에 배열을 이용한 문제는 아님을 알았다. 또한 int 대신 Long을 써야함을 신경써

야한다.

코드 자체는 완성하고 보면 별거 아니지만 좌표를 찾는 방법과 꺾는 수의 경우의 수는 공식을 이용하여 구하여야하는데 그 공식을 찾는 과정이 어려운 문제라고 할 수 있다. 

작성자도 아래의 블로그 글을 참고 하였다.

[BOJ] 백준 1959번 달팽이3 (Java)

 

자바 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class N1959 {
    private static Long N, M;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        M = Long.parseLong(st.nextToken());
        N = Long.parseLong(st.nextToken());

        Long curveSum = findCurveCount();

        Long[] endPos = findEndPosition();

        System.out.println(curveSum);
        System.out.println(endPos[0] + " " + endPos[1]);
    }

    public static Long findCurveCount(){
        if(M > N)
            return (N - 1) * 2 + 1;

        return (M - 1) * 2;
    }

    public static Long[] findEndPosition(){
        // M과 N이 같은 경우
        if(M == N){
            if(M % 2 == 1){
                return new Long[]{(M / 2) + 1, (N / 2) + 1};
            }

            return new Long[] {M / 2 + 1, N / 2};
        }

        // M이 N보다 큰 경우
        if(M > N){
            if(N % 2 == 1){
                return new Long[]{(N / 2) + 1 + (M - N), (N / 2) + 1};
            }

            return new Long[] {N / 2 + 1, N / 2};
        }

        // N보다 M이 큰 경우
        if(M % 2 == 1)
            return new Long[] {(M / 2 + 1), (M / 2 + 1 + (N - M))};

        return new Long[] {M / 2 + 1, M / 2};
    }
}