[BOJ] 15990 1, 2, 3 더하기 5 (Python / 파이썬)

🧷 문제

https://www.acmicpc.net/problem/15990

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 과정에서 같은 수를 두 번 이상 연속해서 사용하지 않는 방법의 수를 구하는 문제이다.

🛠 풀이

이 문제는 DP table을 1차원이 아닌 2차원으로 구성해야 해결할 수 있다.

Step 1.
 먼저 각 인덱스의 DP table을 길이 4의 리스트로 받는데 0번 인덱스에는 n을 만들 수 있는 방법의 수, 1 ~ 3번 인덱스에는 각 인덱스로 끝나는 방법의 수를 넣어준다.
 예를 들면 d[3]의 경우 2 + 1, 1 + 2, 3 이렇게 총 3가지의 경우를 가지고 있고 1, 2, 3으로 끝나는 방법이 각 1개씩 존재하므로 d[3] = [3, 1, 1, 1]로 초기화해준다. 같은 방법으로 d[1] = [1, 1, 0, 0], d[2] = [1, 0, 1, 0]으로 표현할 수 있다.

Step 2.
 d[i], (4 ≤ i)부터는 d[i-1]의 방법의 수에서 끝이 1로 끝나지 않는 경우, d[i-2]에서 끝이 2로 끝나지 않는 경우, d[i-3]에서 끝이 3으로 끝나지 않는 경우를 더하면 된다.
 이걸 코드로 바꿔주면 d[i][1] = d[i-1][0] - d[i-1][1], d[i][2] = d[i-2][0] - d[i-2][2], d[i][3] = d[i-3][0] - d[i-3][3]이다.
 반복을 피하기 위해서 for문을 이용하면 for j in range(1, 4): d[i][j] = d[i-j][0] - d[i-j][j]로 표현 가능하다.

Step 3.
 위에서 d[n]의 0번 인덱스에는 n을 만들 수 있는 방법의 수를 넣어준다고 했으므로, d[n][1] + d[n][2] + d[n][3]의 값을 넣어주고 최종적으로 d[n][0]을 출력하면 원하는 값을 구할 수 있다.

🖊 나의 코드

import sys

input = sys.stdin.readline

if __name__ == "__main__":
    t = int(input())
    d = [[0] * 4 for _ in range(100001)]
    d[1] = [1, 1, 0, 0]
    d[2] = [1, 0, 1, 0]
    d[3] = [3, 1, 1, 1]

    for i in range(4, 100001):
        cnt = 0
        for j in range(1, 4):
            d[i][j] = d[i-j][0] - d[i-j][j]
            cnt += d[i][j]
        d[i][0] = cnt % 1000000009

    for _ in range(t):
        n = int(input())
        print(d[n][0])