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

 

 

백준 15990번: 1, 2, 3 더하기 5

문제 바로 가기

---

📌 문제

정수 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로 나눈 나머지를 출력한다.

 

 

 

 

 

📝 아이디어

이 문제는 정수 $n$을 1, 2, 3의 합으로 나타내는 경우의 수를 구하는 문제입니다. 백준 9095과 비슷하지만 같은 숫자를 두 번 이상 연속해서 사용할 수 없다는 조건이 추가되었기 때문에 마지막에 어떤 숫자를 더했는지 고려해야 합니다.

 

예를 들어 $dp[4]$를 구할 때 마지막 숫자에 따라서 다음의 3가지 경우가 있습니다. 마지막 숫자가 1인 경우에는 그 전에는 2 또는 3이 더해져야 합니다. 마지막 숫자가 2인 경우에는 그 전에는 1 또는 3이 더해져야 합니다. 마지막 숫자가 3인 경우에는 그 전에는 1 또는 2가 더해져야 합니다. 

 

 

 

1. DP 테이블 정의

 

마지막에 더해진 숫자를 기준으로 경우를 나누기 위해 2차원 리스트를 사용하여 DP 테이블을 정의합니다. 

 

$dp[i][j]$는 정수 $i$를 1, 2, 3의 합으로 나타낼 때 마지막 숫자가 $j$로 끝나는 경우의 수를 의미합니다. 여기서 $j$는 1, 2, 3 중 하나입니다.

 

예를 들어 $dp[4][1]$은 숫자 4를 1, 2, 3의 합으로 나타내는 방법 중 마지막 숫자가 1인 경우의 수를 나타냅니다. $dp[4][2]$은 숫자 4를 1, 2, 3의 합으로 나타내는 방법 중 마지막 숫자가 2인 경우의 수를 나타냅니다.

 

이렇게 정의하면 이전 상태를 바탕으로 현재 상태를 구할 수 있으며 중복을 방지할 수 있습니다.

 

 

2. 점화식 도출

 

정수 $i$를 만드는 방법은 마지막 숫자가 무엇인지에 따라 나눌 수 있습니다.

 

마지막 숫자가 1인 경우에는 이전 숫자들의 합은 $i-1$이어야 하며 그 직전에는 2 또는 3만 올 수 있습니다. 

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

 

마지막 숫자가 2인 경우에는 이전 숫자들의 합은 $i-2$이어야 하며 그 직전에는 1또는 3만 올 수 있습니다. 

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

 

마지막 숫자가 3인 경우에는 이전 숫자들의 합은 $i-3$이어야 하며 그 직전에는 1또는 2만 올 수 있습니다. 

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

 

정수 $i$을 1, 2, 3의 합으로 나타내는 방법의 수는 모든 경우를 더하면 되므로 다음과 같습니다.

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

 

 

 

 

 

👩‍💻 나의 답안

MOD = 1000000009

MAX_N = 100000
dp = [[0] * 4 for _ in range(MAX_N + 1)]
dp[1][1] = 1
dp[2][2] = 1
dp[3][1] = dp[3][2] = dp[3][3] = 1

for i in range(4, MAX_N+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

t = int(input())
results = []
for _ in range(t):
    n = int(input())
    results.append((dp[n][1] + dp[n][2]+dp[n][3]) % MOD)

print("\n".join(map(str, results)))