[백준/Python3] 15990 1, 2, 3 더하기 5

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

풀이

특정 수를 1, 2, 3의 합으로 표시할 수 있는 모든 경우의 수를 구하는 문제다. 단, 같은 수를 연속해서 사용할 수는 없다. 즉 4 = 1+2+1은 가능하지만 4 = 1+1+2는 불가능하다는 뜻이다. 때문에 그 수를 만드는 경우의 수와 마지막으로 사용한 수를 모두 저장해야한다. 사용할 수 있는 수는 1, 2, 3 개 이므로 열의 크기가 4인(인덱스를 맞추기위해) 2차원 배열을 만들어 해결한다.

dp[i][j] -> n=i일 때 마지막으로 사용한 수가 j인 경우의 수를 모두 더한 것.

1. n의 경우의 수를 구할 때, 마지막으로 사용할 수로 1로 정할 경우 이 수보다 1 작은 수 중에서 1을 마지막으로 사용하지 않은 경우의 수가 필요하다.
2. 마찬가지로, 마지막으로 사용할 수가 2라고 할 때, 더해지는 것이 2이므로 이 수보다 2 작은 수 중에서 2를 마지막으로 사용하지 않은 경우의 수가 필요하다.
3. 마지막으로 사용할 수를 3으로 할 때, 방법은 위와 같다.

따라서 점화식은 아래와 같이 나타낼 수 있다.

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

최종적으로 n을 만드는 경우의 수는 dp[n][1] + dp[n][2] + dp[n][3]로 나타낼 수 있다.

코드

import sys

# Initial
# n의 최댓값
MAX = 100000
mod = 1000000009

# Make DP table
dp = [[0 for _ in range(4)] for _ in range(MAX + 1)]
# nth -> i / 마지막에 사용한 수 j
dp[1] = [0, 1, 0, 0]
dp[2] = [0, 0, 1, 0]
dp[3] = [0, 1, 1, 1]

for i in range(4, MAX + 1):
    dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % mod
    dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % mod
    dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % mod

# Input n value
for _ in range(int(input())):
    n = int(sys.stdin.readline())
    # Answer
    answer = sum(dp[n]) % mod
    print(answer)