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

#1959 달팽이3

난이도 : 골드 3

유형 : 구현

1959번: 달팽이3

▸ 문제

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

맵의 최대 크기는 21억이기 때문에 완전탐색으로 하면 21억 *21억 연산을 해야할 뿐만 아니라 배열에도 메모리초과로 할당되지 않는다. 그러므로 규칙을 찾아서 풀이를 해야 한다.

 

선이 꺾어지는 횟수

이는 m>n일 때를 살펴보면 n의 크기에 따라 꺾이는 횟수가 결정되는 것을 알 수 있다.

• X 표시가 가장자리부터 시작하여 차례대로 안쪽으로 한 칸씩 줄어들면서 위아래로 총 2개씩 생기는 것을 볼 수 있다. 따라서, 가운데 파란색을 제외한 (n-1)*2개의 셈이 가능하다.
• 추가로 파란색으로 표시된 X를 +1 해주면 된다. 
  • n이 짝수일 때는 n/2+1인 행, n이 홀수일 때, n/2인 행인데 갯수만 세어주므로 신경쓰지 않아도 된다.
• 그냥 갯수만 세어주면 되므로 m>n일 때는 (n-1)*2+1개 이다

m>n일 때

 

반대로, n>=m일 때를 살펴보면 m의 크기에 따라 꺾이는 횟수가 결정되는 것을 알 수 있다.

• X표시가 가장자리부터 차례대로 시작하여 안쪽으로 한 칸씩 줄어들면서 이는 좌우로 총 2개씩 생기는 것을 볼 수 있다.
• 따라서, n>=m일 때는 (m-1)*2개임을 알 수 있다.

n>=m 일 때

끝나는 점의 좌표 찾기

m=n 맵

좌표 또한 조건분기를 통해 각 케이스를 조사해보면 된다. 먼저 가장 간단한 m=n의 끝 점은 다음과 같다.

• m, n이 홀수일 때, 끝 점의 위치는 [(n/2)+1,(n/2)+1] 또는 [(m/2)+1,(m/2)+1] 이다
• m, n이 짝수일 때,  끝 점의 위치는 [(n/2),(n/2)] 또는 [(m/2),(m/2)] 이다

m==n 일 때

 

m>n 맵

m>n인 맵을 살펴보자. x좌표의 값은 판단하기 쉽다. 위에서 구한 m=n인 맵과 구하는 방식이 동일하다.

• n이 홀수일 때 끝점의 x좌표는 n/2+1이다.
• n이 짝수일 때의 끝점의 x좌표는 n/2이다. y좌표또한 n/2+1로 n*n의 끝점 좌표와 동일하다.

m>n

y좌표값은 m=n인 맵과 비교해보면 규칙을 알아내기 쉽다. 아래의 그림을 보면 3x3에서 m의 크기가 1씩 늘어남에 따라 끝점이 아래로 움직이는 모습을 볼 수 있다. 따라서 m*m맵의 끝점 좌표에서 (m-n)의 값을 y좌표에 더한 것이 m>n맵의 끝점 좌표임을 알 수 있다.

• n이 짝수일 때는 n*n 끝점 좌표와 동일하므로, [(n/2+1),(n/2)]이다.
• n이 홀수일 때 끝점의 좌표는 n*n에서 y좌표에 (m-n)만 더해준 값으로 [(n/2+1+(m-n)), (n/2+1)]이다.

 

m<n 맵

m<n는 m>n을 구했으면 단순 90도 회전해서 생각해보면 된다. 따라서 n을 m으로만 변경해주면 끝점 좌표를 쉽게 구할 수 있다.

• m이 짝수일 때는 m*m 끝점 좌표와 동일하므로, [(m/2+1),(m/2)]이다.
• m이 홀수일 때 끝점의 좌표는 m*m에서 x좌표에 (n-m)만 더해준 값으로 [(m/2+1), (m/2+1(n-m)]이다.

 

풀이 코드 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long m = Long.parseLong(st.nextToken());
		long n = Long.parseLong(st.nextToken());
		
		StringBuilder sb = new StringBuilder();
		if(m>n) {
			sb.append(((n-1)*2+1)+"\n");
		}else {
			sb.append(((m-1)*2)+"\n");
		}
		
		if(m==n) {
			if(m%2==1) {
				sb.append((m/2+1)+" "+(n/2+1) +"\n");
			}else {
				sb.append((m/2+1)+" "+(n/2) +"\n");
			}
	 	}else if(m>n) {
	 		if(n%2==0) {
	 			sb.append((n/2+1) +" "+(n/2)+"\n");
	 		}else {
	 			sb.append((n/2+1+(m-n)) +" "+(n/2+1)+"\n");
	 		}
	 	}else {
	 		if(m%2==0) {
	 			sb.append((m/2+1) +" "+(m/2)+"\n");
	 		}else {
	 			sb.append((m/2+1)+" "+(m/2+1+(n-m))+"\n");
	 		}
	 	}
		System.out.println(sb.toString());
	}
}