[알고리즘][백준] 15990번 1, 2, 3 더하기 5 - 파이썬(python) 풀이

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

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

---

9095번 1, 2, 3 더하기와 같이 점화식을 쉽게 만들 수 있을 줄 알고.. 몇십분째 이리저리 고민해봐도 안나와서 보니...

 

2차원으로 해결해야했던 문제..!

 

다른분들 코드를 참고해서 작성했다

import sys

t = int(sys.stdin.readline())

dp = list([0, 0, 0] * 10001)

# 1, 2, 3으로 끝나는 경우

dp[1] = [1, 0, 0]   # 1, X, X

dp[2] = [0, 1, 0]   # X, 2, X

dp[3] = [1, 1, 1]   # 2+1, 1+2, 3

for i in range(4, 100001):

    dp[i][0] = (dp[i-1][1] + dp[i-1][2]) % 1000000009

    dp[i][1] = (dp[i-2][0] + dp[i-2][2]) % 1000000009

    dp[i][2] = (dp[i-3][0] + dp[i-3][1]) % 1000000009

for _ in range(t):

    n = int(sys.stdin.readline())

    print(sum(dp[n]) % 1000000009)

그런데 처음에 dp를 2차원으로 만들어야하는데 코드를 잘못작성했다...

for문으로 바로 수정해주었다.

import sys

t = int(sys.stdin.readline())
dp = [[0, 0, 0] for _ in range(100001)]

# 1, 2, 3으로 끝나는 경우
dp[1] = [1, 0, 0]   # 1, X, X
dp[2] = [0, 1, 0]   # X, 2, X
dp[3] = [1, 1, 1]   # 2+1, 1+2, 3

for i in range(4, 100001):
    dp[i][0] = (dp[i-1][1] + dp[i-1][2]) % 1000000009
    dp[i][1] = (dp[i-2][0] + dp[i-2][2]) % 1000000009
    dp[i][2] = (dp[i-3][0] + dp[i-3][1]) % 1000000009

for _ in range(t):
    n = int(sys.stdin.readline())
    print(sum(dp[n]) % 1000000009)

15990_123더하기5.py

0.00MB