[알고리즘][백준] 11057번 오르막 수 - 파이썬(python) 풀이

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

11057번: 오르막 수

---

2차원으로 마지막 수가 0~9에 따라 뒤에 올 수 있는 수가 다르기 때문에 위와 같은 점화식을 도입했다

import sys

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

if n == 1:
    print(10)
else:
    dp = [[0]*10 for _ in range(n+1)]
    dp[1] = [1] * 10

    for i in range(2, n+1):
        dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4] + dp[i-1][5] + dp[i-1][6] + dp[i-1][7] + dp[i-1][8] + dp[i-1][9]) % 10007
        dp[i][1] = (dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4] + dp[i-1][5] + dp[i-1][6] + dp[i-1][7] + dp[i-1][8] + dp[i-1][9]) % 10007
        dp[i][2] = (dp[i-1][2] + dp[i-1][3] + dp[i-1][4] + dp[i-1][5] + dp[i-1][6] + dp[i-1][7] + dp[i-1][8] + dp[i-1][9]) % 10007
        dp[i][3] = (dp[i-1][3] + dp[i-1][4] + dp[i-1][5] + dp[i-1][6] + dp[i-1][7] + dp[i-1][8] + dp[i-1][9]) % 10007
        dp[i][4] = (dp[i-1][4] + dp[i-1][5] + dp[i-1][6] + dp[i-1][7] + dp[i-1][8] + dp[i-1][9]) % 10007
        dp[i][5] = (dp[i-1][5] + dp[i-1][6] + dp[i-1][7] + dp[i-1][8] + dp[i-1][9]) % 10007
        dp[i][6] = (dp[i-1][6] + dp[i-1][7] + dp[i-1][8] + dp[i-1][9]) % 10007
        dp[i][7] = (dp[i-1][7] + dp[i-1][8] + dp[i-1][9]) % 10007
        dp[i][8] = (dp[i-1][8] + dp[i-1][9]) % 10007
        dp[i][9] = (dp[i-1][9]) % 10007

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

 

 

 

그러나 dp를 2차원으로 하기 싫다면..?!

 

1차원의 방법으로는

import sys

n = int(sys.stdin.readline())
dp = [1] * 10

for i in range(n-1):
    for j in range(1, 10):
        dp[j] += dp[j-1]

print(sum(dp) % 10007)

시간은 똑같지만 훨씬 간단하게 작성할 수 있다

 

11057_오르막수.py

0.00MB