[백준] 1959 - 달팽이3

[문제링크]

1959번: 달팽이3

 

0. 수학 문제

 

노랑 : 시작점 / 파랑 : 회전점 / 빨강 : 종료점

1. 위 그림과 같이n, m크기의 표에서 달팽이가 한바퀴를 이동하면, 총 4번 회전하고 시작점의 (+1, +1)위치에 서게되며, n-2, m-2크기의 표가 된다

 

2. 해당 과정을 n 혹은 m이 3보다 작아질때까지 반복한다

• 즉, n과 m 둘 중 작은쪽이 1 혹은 2가 되는 횟수 x만큼 반복한다
• 각 반복마다 4회 회전이 발생하므로, 이 시점까지 발생한 회전은 4x이다
• 또한 이 시점에서 좌표는 (x, x)이다

 

3. n 혹은 m이 1 혹은 2까지 작아졌다면, 총 6가지 경우의 수가 존재한다

• 1 * 1
• 1 * m
• n * 1
• 2 * 2
• 2 * m (2*2와 회전횟수 / 도착지점은 동일하다)
• n * 2

 

파랑 : 회전점 / 빨강 : 종료점

4. 각 경우마다, 다음과 같은 경로를 거쳐 최종 도착지점에 도달하게 된다

 

5. n과 m의 값을 통해 어떤 경우인지 판단하고, 해당하는 회전 횟수 / 도착지점을 적용한다

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		
		long min = (Math.min(n, m)-1)/2;
		
		long x=min+1,y=min+1;
		long count = 4*min;
		
		n-=2*min;
		m-=2*min;
		if(n==1) {
			y+=m-1;
		}
		else if(m==1) {
			count++;
			x+=n-1;
			
		}
		else if(n==2) {
			count+=2;
			x++;
		}
		else {
			count+=3;
			x++;
		}
		System.out.println(count);
		System.out.println(x+" "+y);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면