[백준 1959번][Java] 달팽이3

www.acmicpc.net/problem/1959

1959번: 달팽이3

입력의 크기가 어마어마하기 때문에 직접 그리면서 화살표가 꺾이는 부분을 일일이 체크할 수 없다(꺾이는 부분을 curve point라고 부르기로 하자). 이럴 경우 규칙을 찾아내 복잡도를 줄이든지 답을 내는 식을 찾든지 해야 된다.

 

자, 이제 다음과 같은 M,N 크기의 사각형이 있다고 하자.

 

사각형의 가장 자리를 다 돌고 이제 빨간색 사각형으로 순회를 시작하려고 한다. 위 그림처럼 내부에 빨간색 사각형처럼 내부에 다른 사각형을 가지는 경우 무조건 커브 포인트 4개가 가장자리에 생기게 돼있다. 이렇게 사각형의 가장 자리를 벗기는 작업을 탈피 라고 정의하자. 탈피는 어떤 종결 조건을 만족하는 사각형을 만날 때까지 일어날 수 있다.

 

이를 식으로 나타내면 

totalCurvePoint = (4 * 탈피 횟수) + (마지막 사각형의 커브 포인트 개수) 가 된다.

 

탈피를 할 수 없는 경우를 생각해보자.

 

위의 네 가지의 경우에는 내부에 다시 탈피를 할 수 없다. 그리고 각 경우의 커브 포인트의 개수도 위와 같다.

이제 커브 포인트의 총 개수 문제는 해결됐다. 

 

M,N 중 작은 값을 선택해 2로 나누면 몫이 탈피 횟수가 된다. (M,N 둘 중 하나가 0이 되는 경우 다시 2를 더해주고 탈피 횟수를 -1 해준다.)  왜 그런지에 대해서 다 설명하면 재미가 없으니 남겨두도록 하겠다.

 

끝나는 포인트를 찾는건 더 간단하다.

탈피를 할 때마다 사각형의 왼쪽 최상위 좌표는 항상 1씩 동시에 늘어난다. 최초에 (1,1)에서 시작했다면 다음은 (2,2)가 되는 식이다.

마지막으로 탈피한 사각형의 왼쪽 최상위 좌표는 (1+탈피 횟수, 1+탈피 횟수)가 된다. 이 좌표를 기준으로 위의 네 가지 종결 케이스를 보고 마지막 좌표를 찾으면 된다. 

 

 

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

/*
달팽이3
https://www.acmicpc.net/problem/1959
 */
public class Main {
	static long m,n;
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader();
//		InputReader reader = new InputReader("testcase.txt");
		StringTokenizer st = new StringTokenizer(reader.readLine());
		m = Long.parseLong(st.nextToken());
		n = Long.parseLong(st.nextToken());

		long smallerValue = Math.min(m,n);
		long quotient = smallerValue / 2;
		m -= quotient*2; n -= quotient*2;
		if(m == 0 || n == 0) {
			quotient--;
			m += 2; n += 2;
		}

		long curveCnt = 4*quotient + lastSnail(m,n);
		int row = 1; int col = 1;
		row += quotient; col += quotient;
		if(m == 2 || n == 2) {
			row++;
		}
		if(m == 1) {
			col += n-1;
		}
		if(n == 1){
			row += m-1;
		}

		System.out.println(curveCnt);
		System.out.println(row + " " + col);
	}

	private static long lastSnail(long m, long n) {
		if(m == 2) return 2;
		if(n == 2) return 3;

		if(m == 1) return 0;
		if(n == 1) return 1;

		return 0;
	}
}
class Point {
	int row, col;
	public Point(int row, int col) {
		this.row = row;
		this.col = col;
	}
}

class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}