[백준] 15990. 1, 2, 3 더하기 5(Python, 파이썬)

백준 온라인의 문제 풀이입니다.

📖 [백준] 15990. 1, 2, 3 더하기 5

시간 제한	메모리 제한	난이도
1초	512 MB	실버 2

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

✔️ 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

✔️ 출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

✔️ 입력 출력 예시

입력	출력
3 4 7 10	3 9 27

🗒️ 내 풀이

‘1,000,000,009로 나눈 나머지를 출력한다.’라는 문구에서 다이나믹 프로그래밍 문제구나 하고 다이나믹 프로그래밍으로 접근했다. 처음엔 1차원으로만 생각하다보니, 해결 방법이 떠오르지 않았다. 그러다 같은 수를 두 번 연속 사용하지 않는다는 조건에서 2차원 배열로 접근했다. dp 테이블에서 index 1, 2, 3 번째는 각각 합이 1, 2, 3으로 끝나는 경우의 수라고 했을 때, 점화식은 다음과 같다.

• dp[n][1] = dp[n-1][2] + dp[n-1][3] = sum(dp[n - 1]) - dp[n - 1][1]
• dp[n][2] = dp[n-2][1] + dp[n-2][3] = sum(dp[n - 2]) - dp[n - 2][2]
• dp[n][3] = dp[n-3][1] + dp[n-3][2] = sum(dp[n - 3]) - dp[n - 3][3]

따라서 이를 구현하면 아래와 같다.

import sys
input = sys.stdin.readline
MOD = 1000000009

n = int(input())
data = [int(input()) for _ in range(n)]

dp = [[0] * 4 for i in range(max(data) + 1)]

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

# dp[n][1] = dp[n-1][2] + dp[n-1][3] = sum(dp[n - 1]) - dp[n - 1][1]
# dp[n][2] = dp[n-2][1] + dp[n-2][3] = sum(dp[n - 2]) - dp[n - 2][2]
# dp[n][3] = dp[n-3][1] + dp[n-3][2] = sum(dp[n - 3]) - dp[n - 3][3]
for i in range(4, max(data) + 1):
    for k in range(1, 4):
        dp[i][k] = (sum(dp[i - k]) - dp[i - k][k]) % MOD
        
for d in data:
    print(sum(dp[d]) % MOD)