[백준 3101] 토끼의 이동

문제 링크 : https://www.acmicpc.net/problem/3101

이 문제는 주어진 격자의 규칙을 파악하면 풀 수 있는 문제입니다.

처음 이 문제를 이중 ArrayList를 이용하여 대각선 별로 데이터를 채워 넣는 방식으로 접근했으나 N이 10만 가량 되기 때문에 NXN을 모두 채우면 메모리 초과가 발생합니다. 따라서 규칙을 찾아 적용하는 방법을 생각해야 합니다.

https://nahwasa.com/entry/%EC%9E%90%EB%B0%94-%EB%B0%B1%EC%A4%80-3101-%ED%86%A0%EB%81%BC%EC%9D%98-%EC%9D%B4%EB%8F%99-java
저는 위의 블로그를 참고하여 문제를 풀었습니다. 현재 토끼의 위치를 다음과 같이 나타낼 수 있습니다.

토끼의 위치 = 대각선 시작값 + 상하좌우로 이동한 보정값

이렇게 진행한 이유는 각 대각선의 시작값이 공차가 n인 등차수열이기 때문입니다. (a_n = a_n-1 + n) 각 대각선의 시작값은 1,2,4,7... 이런 식으로 확장하기 때문에 등차수열이 성립합니다.

하지만 주의할 점은 증가하는 등차수열은 N번째 대각선까지만 적용된다는 것입니다. N번째 대각선 이후는 감소하는 등차수열이 됩니다. (a_n = a_n+1 - n)

이를 토대로 dp[i] = i+1번 대각선(제일 처음 1의 경우 1번 대각선으로 간주했을 때)의 시작값 으로 설정할 수 있으며 값을 모두 채워넣을 수 있습니다. 이 경우 i는 2N-2까지 진행되기 때문에 메모리 초과가 발생하지 않습니다.

이후 보정값에 대해 알아봅시다. 토끼의 좌표가 y,x라고 했을 때 토끼는 y+x+1번 대각선에 위치합니다. 이 때 i+1이 홀수일 경우(1번, 3번 ... 대각선) 아래에서 위로 증가하는 방향을 나타내며 i+1이 짝수일 경우(2번, 4번 ... 대각선) 위에서 아래로 감소하는 방향을 나타냅니다.

하나의 예를 들어봅시다. 만약 N이 충분히 큰 상황에서 (y,x) = (0,1)의 값이 아래로 이동하면 어떤 값을 나타낼까요? 나타나는 좌표는 (1,1)으로 i가 짝수인 대각선으로(i = y+x) 이동함과 동시에 대각선의 시작에서 1칸 앞서게 됩니다. 그럼 오른쪽으로 이동하면 어떻게 될까요? (0,2)로 이동함과 동시에 대각선의 시작에서 2칸 앞서게 됩니다.

그럼 i가 홀수인 대각선으로 이동하는 경우도 살펴봅시다. (y,x) = (0,2)의 값이 아래로 이동할 경우 i가 홀수인 대각선으로 이동하며 (1,2)의 좌표를 가집니다. 이 때 시작값에서 1만큼 떨어지게 됩니다. 이어서 오른쪽으로 이동할 경우 (0,3)으로 이동하며 시작값에서 0만큼 떨어지게 됩니다.

여기서 규칙을 발견하셨나요? 즉 (y,x)가 홀수 대각선에 존재하는 경우, 즉 (y+x)%2==1인 경우 짝수 대각선으로 이동하면서 대각선 시작값보다 y만큼 멀어지게 됩니다. 반대로 (y,x)가 짝수 대각선에 존재하는 경우, 즉 (y+x)%2==0인 경우 홀수 대각선으로 이동하면서 대각선 시작값보다 x만큼 멀어지게 됩니다. 따라서 보정값은 (y+x)%2==0 ? x : y로 정의할 수 있습니다.

하지만 이 값 역시 i+1이 N까지만 적용됩니다. 이후는 감소하는 등차수열이기 때문에 적용이 다르게 되기 때문이죠. 감소하는 경우는 다르게 보아야 합니다. 만약 N=6인 격자에서 (y,x) = (2,4)일 경우 아래로 이동하는 경우를 보겠습니다. i가 짝수 대각선에서 홀수로 이동하며 (3,4)로 이동하며 시작값에서 1만큼 떨어집니다. 오른쪽으로 이동하는 경우 (2,5)로 이동하며 시작값에서 0만큼 떨어집니다.

i가 홀수인 경우도 보겠습니다. (y,x) = (3,4)에서 아래로 이동하는 경우 (4,4)가 되며 시작값에서 1만큼 떨어집니다. 오른쪽으로 이동하는 경우 (3,5)가 되며 시작값에서 2만큼 떨어집니다.

여기서도 규칙을 발견하셨나요? 감소하는 수열에서는, 즉 y+x(=i) >=N 인 경우 짝수 대각선에서 홀수로 이동할 경우 시작값보다 N-1-y만큼 멀어지게 되며, 홀수에서 짝수로 이동하는 경우 시작값보다 N-1-x만큼 멀어지게 됩니다. 여기서 포인트는 감소하는 수열에서는 증가하는 수열과 반대로 짝수에서 홀수로 이동하는 경우 y값에 영향을 받으며 홀수에서 짝수로 이동하는 경우 x값에 영향을 받는다는 것입니다. 따라서 이 경우 단순히 값을 다르게 처리하는 것 뿐만 아니라 y와 x값을 반대로 적용해야 합니다.

다음은 코드입니다.

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

class Main{
    static int N,K;
    static long[] dp;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        String str = br.readLine();

        // dp[i] = i+1번 대각선의 시작값
        // 각 대각선의 시작 수열 : 1,2,4,7,... --> a_n = a_n-1 + n
        // i+1 <= N 까지는 증가하는 수열
        dp = new long[2*N-1];
        dp[0] = 1;
        for(int i=1;i<N;i++) dp[i] = dp[i-1]+i;

        // i+1 > N 부터는 감소하는 수열
        // a_n = a_n+1 - n
        dp[2*N-2] = (long) N *N;
        for(int i=2;i<N;i++) dp[2*N-i-1] = dp[2*N-i]-i;

        Rabbit rabbit = new Rabbit();
        for(int i=0;i<K;i++){
            char d = str.charAt(i);
            rabbit.move(d);
            rabbit.setScore();
        }

        System.out.println(rabbit.score);
    }

    static class Rabbit{
        int y = 0;
        int x = 0;
        long score = 1;

        Rabbit(){}

        void move(char d){
            switch (d){
                case 'U':
                    y--;
                    break;
                case 'D':
                    y++;
                    break;
                case 'L':
                    x--;
                    break;
                case 'R':
                    x++;
                    break;
            }
        }

        void setScore(){
            score += dp[y+x] + correction(y,x);
        }

        int correction(int y, int x){
            if (y+x >= N) {
                y = N-1-y;
                x = N-1-x;
                int tmp = y;
                y = x;
                x = tmp;
            }
            return (y+x)%2==0 ? x : y;
        }
    }
}