17069 - 파이프 옮기기 2

파이프 옮기기 1과 문제는 같으나 제한시간이 0.5초이고 N이 $3 \le N \le 32$ 범위로 더 커졌다.

따라서 이 문제에서 이전처럼 브루트포스 방식으로 푼다면 시간초과가 날 것이다. 따라서 다른 방식으로 풀어야 한다.

잘 생각해보면 (i, j)까지 이동하는 방법의 수를 점화식을 이용해 정의할 수 있을 것 같다. 먼저 dp 배열의 형태와 의미를 정의해보자.

$(i, j)$를 위치, $k$ (0=가로, 1=세로, 2=대각선)를 방향으로 두면

$$dp[i][j][k] = (\text{k방향으로 파이프의 끝을 (i,j)에 둘 수 있는 경우의 수})$$

그렇다면 최초의 위치에서 (1, 2)에 가로 방향으로 파이프의 끝을 둘 수 있으므로

$$dp[1][2][0] = 1$$

이다.

이제 방향별로 점화식을 세워보자. (i,j)에 가로 방향으로 파이프를 두려면 이전에 파이프가 가로였거나 대각선 상태였어야 한다. 한편 세로로 두려면 파이프가 세로였거나 대각선 상태였어야 한다. 대각선의 경우는 가로, 세로, 대각선 모두 가능하다. 이러한 사실과 그림에서 파이프의 위치를 잘 관찰하면 아래와 같은 점화식을 도출할 수 있다.

$$dp[i][j][k] = \begin{cases} dp[i][j-1][0] + dp[i][j-1][2] && (k = 0) \\ dp[i-1][j][1] + dp[i-1][j][2] && (k = 1) \\ dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2] && (k = 2) \end{cases}$$

한편 가로, 세로 이동은 $(i, j)$번째 칸이 비어있어야 하고, 대각선 이동은 $(i, j)$, $(i-1, j)$, $(i, j-1)$ 이 모두 비어있어야 하므로 이를 코드에서 검사해야 한다.

아래 코드가 위 점화식을 반영해 각 위치별 경우의 수를 계산하는 로직이다. 여기서 j = 3부터 도는 이유는 j <= 2까지는 파이프를 가로로 더 이동시키거나 세로, 대각선으로 돌려 밀 수 있는 방법이 하나도 없기 때문이다.

또한 배열의 초기값이 0이고 1-based indexing을 사용하고 파이프의 방향별로 나뉘어져 있기 때문에 각 점화식별로 경계 조건을 if문으로 처리할 필요가 없다.

    dp[1][2][0] = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = 3; j <= N; j++) {
            if (arr[i][j]) continue;
            dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]; 
            dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2];  
            if (!arr[i-1][j] && !arr[i][j-1]) 
                dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2];
            
        }
    }

🔗 문제 링크

전체 코드

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());

        boolean arr[][] = new boolean[N+5][N+5];
        long dp[][][] = new long[N+5][N+5][3];
        StringTokenizer st;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                arr[i][j] = (Integer.parseInt(st.nextToken()) > 0);
            }
        }
        dp[1][2][0] = 1;
        for (int i = 1; i <= N; i++) {
            for (int j = 3; j <= N; j++) {
                if (arr[i][j]) continue;
                dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]; 
                dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2];  
                if (!arr[i-1][j] && !arr[i][j-1]) 
                    dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2];
                
            }
        }
        bw.write((dp[N][N][0] + dp[N][N][1] + dp[N][N][2]) + "\n");
        bw.flush();
    }
}

시간복잡도

시간복잡도는 $N \times (N-2)$ 배열을 순회하므로 $O(N^2-2N) = O(N^2)$ 의 시간복잡도이다. $(32)^2 = 1024$이므로 0.5초 내에 통과할 수 있다.