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

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

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

코드 작성

dp = [[0 for _ in range(3)] for _ in range(100001)]
dp[1] = [1,0,0]
dp[2] = [0,1,0]
dp[3] = [1,1,1]
mod = 1000000009
for i in range(4, 100001):
    dp[i][0] = (dp[i-1][1] + dp[i-1][2])%mod
    dp[i][1] = (dp[i-2][0] + dp[i-2][2])%mod
    dp[i][2] = (dp[i-3][0] + dp[i-3][1])%mod
n = int(input())
for _ in range(n):
    num = int(input())
    print(sum(dp[num])%mod)

풀이

#1. 문제풀이

이 문제는 2중 리스트를 만들어서 dp[n]이라는 숫자 n에 각 끝 자리수 1,2,3을 기준으로 [?, ?, ?]으로 기록한다.

예를들어 dp[4]에서 4라는 숫자는

3+1과 1+2+1로써 끝자리 1이 2개 있으며

1+3으로 끝자리 3이 1개 있다.

즉, dp[4] = [2,0,1] 로써 표현할 수 있다.

 

#2. 초기값

dp = [[0,0,0], [0,0,0], [0,0,0], [0,0,0] ... [0,0,0]]

dp[1], dp[2], dp[3]은 각각 [1,0,0], [0,1,0], [1,1,1]로 나타내는데

dp[3]은 2+1, 1+2, 3이므로 [1,1,1]이 된다.

 

#3. 전체 식

dp[i][0]은 dp[i-1]에서 인덱스 1에 있는 숫자를 더해준 개수와, i-1에서 인덱스2의 개수의 합이다. 이 방법이 이해가 되지 않을 경우

https://tkaghks1.tistory.com/81

에서 1,2,3 더하기 문제를 다시 이해하는 것이 필요하다.

 

여기서 헷갈리지 말아야 할게 문제에서 숫자를 1,2,3으로 표현하는데 인덱스는 0,1,2로 나타내기 때문이다.

 

#4. 1000000009로 나눈 값

코드식을 각각의 수로 나누면 지저분해 보여서

mod = 1000000009로 지정하였고, 매 숫자마다 나머지로 나누었다.