[백준] 오르막 수

출처::  www.acmicpc.net/problem/11057

분류:: dp

 

1. 문제 이해 및 해결과정

dp[i] : 길이가 i인 오르막 수의 개수 끝이 0일경우, 0        1일경우,  앞에 올 수 있는 것 0 1        2일 경우, 앞에 올수 있는 것 0 1 2      0   1   2   3   4   5   6   7   8   9     1    1   1   1   1   1   1   1   1   1   1 2    1   2   3   4    5   6   7  8   9   10  dp[2][3]=dp[1][0]+dp[1][1]+dp[1][2] =>2자리 이면서 3으로 끝나는 것  3    1   3   6  10   15  21 28 36 45 55  dp[i][j] = dp[i-1][0]+dp[i-1][1]+ .... + dp[i-1][j] => dp[i][j]=dp[i-1][j]+dp[i][j-1]

 

2. 풀이방법

  1. dp

#오르막 수
#https://www.acmicpc.net/problem/11057
import sys
sys.stdin = open("input.txt","r")
n=int(input())
dp=[[1]*10 for _ in range(n+1)]
mod=10007
for i in range(1,n+1):
    for j in range(1,10):
        dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
print(sum(dp[n-1])%mod)

 

3. 오답원인

- mod 로 꼭 나누어 주어야 한다. 

 

4. 알게된 점