1411. Number of Ways to Paint N × 3 Grid

[zeikar]

Problem link

https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/

Problem Summary

3개의 색을 사용해서 n x 3 크기의 그리드를 인접한 색이 같지 않도록 색칠하는 경우의 수를 구하는 문제.

Solution

딱 보니 DP이다.

색의 조합이 한정되어 있으므로 이를 배열로 넣어주고 DP를 돌리면 된다.

DP[i][j] = DP[i - 1][k] (k는 j와 이웃하는 색이 같지 않은 색의 조합)

위 DP풀이는 O(n)이라 충분히 통과하지만 (정확히는 색의 조합 k, n * k * k) O(log n)으로도 가능한데... 행렬의 곱셈을 이용하면 된다!
https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/discuss/575485/C%2B%2BPython-O(logN)-Time

Source Code

class Solution:
    def numOfWays(self, n: int) -> int:
        dp = [[0] * 12 for i in range(n + 1)]

        color = [[0, 1, 0],
                 [0, 1, 2],
                 [0, 2, 0],
                 [0, 2, 1],
                 [1, 0, 1],
                 [1, 0, 2],
                 [1, 2, 0],
                 [1, 2, 1],
                 [2, 0, 1],
                 [2, 0, 2],
                 [2, 1, 0],
                 [2, 1, 2]]

        for i in range(1, n + 1):
            for j in range(len(color)):
                colors = [color[j][0], color[j][1], color[j][2]]

                if i == 1:
                    dp[i][j] = 1
                    continue

                for k in range(len(color)):
                    prev_colors = [color[k][0], color[k][1], color[k][2]]

                    if colors[0] == prev_colors[0] or colors[1] == prev_colors[1] or colors[2] == prev_colors[2]:
                        continue

                    dp[i][j] += dp[i - 1][k]

        return sum(dp[n]) % (10 ** 9 + 7)