[CodeGround] Practice - 미궁 속의 방

문제 본문

입력

첫 번째 줄에 테스트 케이스의 수 T 가 주어진다. (1≤T≤50)
각 테스트 케이스의 첫 번째 줄에는 격자의 크기 N과 경근이가 움직인 횟수 K 가 주어진다.
(1≤N≤100000, 1≤K≤300000)
각 테스트 케이스의 두 번째 줄에는 경근이의 움직임이 문자열로 주어진다. 문자열은 'U', 'D', 'L', 'R'로만 이루어지며,
U는 위쪽, D는 아래쪽,  L은 왼쪽, R은 오른쪽으로 움직였음을 의미한다.
주어지는 입력으로 인해 경근이가 미궁을 벗어나지 않는다는 것을 보장한다.

제한시간

1초(Java 2초)

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 번째 줄에 “Case #T”를 출력하여야 한다. 이 때 T는 케이스의 번호이다. 
각 테스트 케이스마다 두 번째 줄에 경근이가 방문한 모든 방의 번호의 합을 출력한다.
이 때, 답이 32비트 정수 범위를 넘어갈 수 있음에 주의하도록 한다.

풀이

이 문제의 핵심은, 미궁의 각 방에 적힌 수를 알아내는 것이다. 미궁을 N by N 배열 array 라 했을때, array[i][j] 가 무었인지 상수시간 혹은 log(N) 이내에 알아내야 한다. 미궁의 각 방은 대각선순서로 값이 정해지므로, 규칙은 분명 대각선을 바라보면 찾을 수 있을 것이다.

N=5 일때 미궁

우선, i + j <= N - 1 에서는, i + j 가 증가할수록  i + j가 같은 원소들의 수가 늘어나고, i + j >=N 인 경우 반대로 줄어든다. 따라서, 두 가지의 경우에서 다른 규칙을 갖게 될 것이다.  

i + j <= N - 1 인 경우, 각 array[i][j]는 sigma(i + j) < array[i][j] <=sigma(i + j +1) 을 만족한다. 또한, i + j 가 1 씩 커질때마다, 각 라인에서 값이 커지는 방향이 반대로 바뀐다. 즉, 다음과 같은 로직이 성립한다.

if((i+j)%2==1) {
	long start = sigma(i+j)+1;
	array[i][j] = start+i;
}else {
	long start = sigma(i+j)+1;
	array[i][j] = start+j;
}

이제, i + j >= N 인 경우를 살펴보자. 이 경우, 반대로 N^2 에서, 숫자를 빼는 방식으로 규칙을 설명할 수 있다. 자세히 말하면, i + j = 2 * (N - 1) - 1 인 경우,

array[i][j]는 N^2 - sigma(-1 * (i + j - 2 * (N - 1))) <= array[i][j] < N^2 - sigma(-1 * (i + j - 2 * (N - 1)-1))

이 성립한다. 쉽게 보기위해, sigma(K) 에서 K 가 음수일 경우 -1 * K에 대해 누적합을 구한다 하면,

array[i][j]는 N^2 - sigma((i + j - 2 * (N - 1)) <= array[i][j] < N^2 - sigma(i + j - 2 * (N - 1)-1) 이 성립한다. 또한, 이 경우에도 i + j 가 짝수이냐 홀수이냐에 따라 각 라인에서 값이 커지는 방향이 바뀌므로 다음과같은 로직이 성립한다.

if((i+j)%2==1) {
	long start = sigma(i+j-(n+n-2));
	array[i][j] = n*n -(start+j-(i+j-n+1));
}else {
	long start = sigma(i+j-(n+n-2));
	array[i][j] = n*n -(start+i-(i+j-n+1));
}

이제, 위에서 보인 로직을 통해 미궁의 각 방의 숫자를 상수시간내에 알 수 있게되었다. 그 후 U, D, L, R로 구성된 문자열을 한글짜씩 때서 i, j 를 적절히 변형시켜 위 로직에 대입해 나온 값을 합산하면 된다. 이 때, 시작점이 값이 1인 방이므로, 1부터 합산을 해야한다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Solution {
	static int Answer;

	public static void main(String args[]) throws Exception	{
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for(int test_case = 0; test_case < T; test_case++) {
			int n = sc.nextInt();
			int k = sc.nextInt();
			String op = sc.next();
			int x=0,y=0;
			long sum =1;
			for(int i=0;i<op.length();i++) {
				char a = op.charAt(i);
				if(a=='U') {
					x--;
				}else if(a=='D') {
					x++;
				}else if(a=='L') {
					y--;
				}else if(a=='R') {
					y++;
				}
				sum+=getNum(x, y, n);
			}
			System.out.println("Case #"+(test_case+1));
			System.out.println(sum);
		}
	}
	private static long sigma(int n) {
		if(n<0)n = n*-1;
		return n*(n+1)/2;
	}
	private static long getNum(int i,int j, int n) {
		if(i+j<=n-1) {
			if((i+j)%2==1) {
				long start = sigma(i+j)+1;
				return start+i;
			}else {
				long start = sigma(i+j)+1;
				return start+j;
			}
		}else {
			if((i+j)%2==1) {
				long start = sigma(i+j-(n+n-2));
				return n*n -(start+j-(i+j-n+1));
			}else {
				long start = sigma(i+j-(n+n-2));
				return n*n -(start+i-(i+j-n+1));
			}
		}
	}
}