[백준] 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); } }

결과 화면

from http://nato-blog.tistory.com/148 by ccl(S) rewrite - 2021-11-05 08:01:50