[프로그래머스 JAVA] 12900. 2 x n 타일링

문제 링크

---

프로그래머스

접근 방법

---

2 x n 크기의 직사각형을 1 x 2 타일로 채우는 경우의 수를 구해야 합니다.

처음에는 마지막에 놓는 타일의 방향을 기준으로 경우를 나누었습니다.
마지막에 가로 타일을 놓는 경우와 세로 타일을 놓는 경우를 각각 다른 상태로 관리합니다.

tile[i][0]은 가로 타일로 끝나는 경우의 수입니다.
가로 타일은 위아래로 2개가 함께 놓여야 하므로, 이전에 i - 2 위치까지 채운 상태에서 이어질 수 있습니다.

tile[i][1]은 세로 타일로 끝나는 경우의 수입니다.
세로 타일은 한 칸만 차지하므로, 이전에 i - 1 위치까지 채운 상태에서 이어질 수 있습니다.

따라서 마지막 타일의 형태를 기준으로 가로로 끝나는 경우와 세로로 끝나는 경우를 나누어 DP 배열에 저장합니다.
최종적으로는 두 경우를 더한 값이 전체 경우의 수가 됩니다.

소스 코드

---

class Solution {
    public int solution(int n) {
        int[][] tile = new int[n + 2][2]; // 0 가로 1 세로

        tile[0][1] = tile[1][1] = 1; // 세로
        tile[1][0] = 1; // 가로 끝지점

        for (int i = 2; i < n; i++) {
            tile[i][0] = (tile[i - 2][1] + tile[i - 2][0]) % 1000000007;
            tile[i][1] = (tile[i - 1][1] + tile[i - 1][0]) % 1000000007;
        }

        return (tile[n - 1][0] + tile[n - 1][1]) % 1000000007;
    }
}

코드 설명

---

tile 배열은 마지막에 놓인 타일의 방향을 기준으로 경우의 수를 저장합니다.

int[][] tile = new int[n + 2][2];

tile[i][0]은 가로 타일 2개를 위아래로 놓아 끝나는 경우입니다.
tile[i][1]은 세로 타일 1개를 놓아 끝나는 경우입니다.

tile[0][1] = tile[1][1] = 1;
tile[1][0] = 1;

초기값을 설정합니다.
tile[0][1]은 이후 점화식 계산을 위한 시작값입니다.
tile[1][1]은 세로 타일만 놓는 경우이고, tile[1][0]은 가로 타일 2개를 놓아 끝나는 경우입니다.

tile[i][0] = (tile[i - 2][1] + tile[i - 2][0]) % 1000000007;

가로 타일로 끝나는 경우를 계산합니다.
가로 타일은 너비를 2칸 차지하므로 i - 2 위치까지 채운 전체 경우에서 이어집니다.
따라서 tile[i - 2][1] + tile[i - 2][0]을 더합니다.

tile[i][1] = (tile[i - 1][1] + tile[i - 1][0]) % 1000000007;

세로 타일로 끝나는 경우를 계산합니다.
세로 타일은 너비를 1칸 차지하므로 i - 1 위치까지 채운 전체 경우에서 이어집니다.
따라서 tile[i - 1][1] + tile[i - 1][0]을 더합니다.

return (tile[n - 1][0] + tile[n - 1][1]) % 1000000007;

마지막에는 가로 타일로 끝나는 경우와 세로 타일로 끝나는 경우를 더해 전체 경우의 수를 반환합니다.
현재 코드는 인덱스를 n - 1 기준으로 계산하므로 tile[n - 1][0] + tile[n - 1][1]을 반환합니다.

개선점

---

위 코드에서 얻을 수 있는 핵심 인사이트는 tile[i][0]과 tile[i][1]의 합이 결국 해당 위치까지 타일을 채우는 전체 경우의 수라는 점입니다.

현재 풀이의 반환값은 다음과 같습니다.

tile[n - 1][0] + tile[n - 1][1]

예를 들어 n = 4라면 다음 값을 구해야 합니다.

tile[3][0] + tile[3][1]

기존 점화식에 따라 전개하면 다음과 같습니다.

tile[3][0] = tile[1][1] + tile[1][0]
tile[3][1] = tile[2][1] + tile[2][0]

tile[2][1]은 다시 다음처럼 전개됩니다.

tile[2][1] = tile[1][1] + tile[1][0]

그리고 tile[1][1]도 초기값 기준으로 다음처럼 볼 수 있습니다.

tile[1][1] = tile[0][1] + tile[0][0]

따라서 tile[3][1]은 다음처럼 정리할 수 있습니다.

tile[3][1] = tile[2][0] + tile[1][0] + tile[0][0] + tile[0][1]

tile[3][0]도 같은 방식으로 전개하면 다음과 같습니다.

tile[3][0] = tile[1][0] + tile[0][0] + tile[0][1]

여기서 tile[0][1] = 1입니다.
즉, 세로 상태인 tile[i][1]도 계속 전개하면 가로 상태와 초기값으로 표현할 수 있습니다.

이 흐름을 더 단순하게 보면, 두 상태의 합은 다음처럼 하나의 전체 경우의 수로 볼 수 있습니다.

dp[i] = tile[i][0] + tile[i][1]

기존 점화식은 다음과 같습니다.

tile[i][0] = tile[i - 2][1] + tile[i - 2][0]
tile[i][1] = tile[i - 1][1] + tile[i - 1][0]

이를 dp 기준으로 바꾸면 다음과 같습니다.

tile[i][0] = dp[i - 2]
tile[i][1] = dp[i - 1]

따라서 전체 경우의 수는 다음처럼 정리됩니다.

dp[i] = tile[i][0] + tile[i][1]
dp[i] = dp[i - 2] + dp[i - 1]

결국 다음과 같은 피보나치 형태의 점화식이 됩니다.

dp[i] = dp[i - 1] + dp[i - 2]

처음에는 마지막 타일의 방향에 따라 2차원 DP로 나누어 계산했지만, 전개해보면 현재 경우의 수는 이전 한 칸의 경우의 수와 이전 두 칸의 경우의 수의 합입니다.
따라서 1차원 DP로 개선할 수 있습니다.

개선 코드

---

class Solution {
    public int solution(int n) {
        int MOD = 1000000007;

        int[] dp = new int[n + 2];

        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }

        return dp[n];
    }
}