오르막 수

문제분석

점화식을 찾아보자!

위의 표에서 가로는 숫자의 자리수, 세로는 해당 숫자로 끝나는 수의 개수를 의미한다.

• 한자리수 숫자에 대해서는 0부터 9까지 각 숫자로 끝나는 숫자의 개수가 모두 1개씩이다.
• 두자리수 숫자에 대해 생각해보자. 1로 끝나는 숫자의 개수는 0으로 끝나는 한자리수 숫자, 1로 끝나는 한자리수, 숫자에 각각 1을 추가해 더한 개수이다. 따라서 (1+1=2) 2개다.
• 마찬가지로 2로 끝나는 두자리수 숫자의 개수는 (1+1+1=3) 3개이고, 이러한 방식으로 3~9로 끝나는 두자리수 숫자의 개수도 구할 수 있다.
• 세자리수에 대해서도 동일하다. 해당 숫자 이하의 숫자로 끝나는 두자리수들의 개수를 모두 더하면 되는 것이다.

점화식으로 다음과 같이 나타낼 수 있다. dp[i][j]=dp[i-1][j]+dp[i][j-1]

여기에 문제에 주어진 조건(10007로 나눈 나머지를 출력한다.)을 적용해 코드를 작성하면 된다!

CODE

import sys
read=sys.stdin.readline

n=int(read())
dp=list(list(0 for _ in range(10)) for _ in range(n+1))

for i in range(10):
    dp[1][i]=1
for i in range(n+1):
    dp[i][0]=1

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

print(sum(dp[-1])%10_007)

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]