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

문제

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

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

---

문제 요약

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1000000009로 나눈 나머지를 출력한다.
 
+ 같은 수를 두 번 이상 연속해서 사용하면 안된다.

---

코드

T = int(input())

dp = [[0, 0, 0] for _ in range(100001)]
# dp[i][0]: i를 1, 2, 3으로 나타낸 수 중 1로 끝나는 경우의 수
# dp[i][1]: i를 1, 2, 3으로 나타낸 수 중 2로 끝나는 경우의 수
# dp[i][2]: i를 1, 2, 3으로 나타낸 수 중 3으로 끝나는 경우의 수

dp[1] = [1, 0, 0]
dp[2] = [0, 1, 0]
dp[3] = [1, 1, 1]

for i in range(4, 100001):
    dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % 1000000009
    # i - 1을 1, 2, 3으로 나타낸 방법 중 2와 3으로 끝난 방법 끝에 + 1을 한 경우
    
    dp[i][1] = (dp[i - 2][0] + dp[i - 2][2]) % 1000000009
    # i - 2을 1, 2, 3으로 나타낸 방법 중 1과 3으로 끝난 방법 끝에 + 2를 한 경우

    dp[i][2] = (dp[i - 3][0] + dp[i - 3][1]) % 1000000009
    # i - 3을 1, 2, 3으로 나타낸 방법 중 1과 2로 끝난 방법 끝에 + 3을 한 경우

for _ in range(T):
    n = int(input())
    print(sum(dp[n]) % 1000000009)

---

코드 설명

1. i를 1, 2, 3의 합으로 나타낸 수를 1, 2, 3으로 끝나는 세 가지 경우로 구분하여 저장하는 2차원 메모이제이션 테이블 dp를 생성한다.
ex) 4: 1 + 2 + 1은 1로 끝나는 경우, 1 + 3은 3으로 끝나는 경우이다.
 
2. 반복문을 통해 dp[i]를 계산한다.
 
2 - 1. dp[i][0]  = i를 1, 2, 3으로 나타낸 방법 중 1로 끝나는 경우
=> i - 1을 1, 2, 3으로 나타낸 방법 중 2와 3으로 끝난 방법 끝에 + 1을 한 경우
 
2 - 2. dp[i][1]  = i를 1, 2, 3으로 나타낸 방법 중 2로 끝나는 경우
=> i - 2을 1, 2, 3으로 나타낸 방법 중 1과 3으로 끝난 방법 끝에 + 2을 한 경우
 
2 - 3. dp[i][2]  = i를 1, 2, 3으로 나타낸 방법 중 3로 끝나는 경우
=> i - 3을 1, 2, 3으로 나타낸 방법 중 1과 2로 끝난 방법 끝에 + 3을 한 경우
 
4. dp[n[0] + dp[n][1] +dp[n][2]를 1000000009로 나눈 값을 출력한다.