[백준 11057 오르막 수 문제] PYTHON

이 문제는 먼저 규칙을 파악해야 한다.

 

N=2 일 때

00 11 ~
01 12
02 13
03 14
04 ~
~  19
09 
SUM: 10+9+8+7 ~ +1 = 55

 

N=3 일 때
000  111
001  112
002  113
003  114
004  115
005  116
~     ~
099  199
SUM: 55+45+36+28+21+15+10+6+3+1 = 220

 

맨 앞자리에 들어올 수 있는 숫자는 0부터 9까지 총 10개이다.

맨 앞자리에 들어오는 수를 기준으로 가질 수 있는 숫자의 갯수를 배열로 표현하면

N=2일때 [10,9,8,~,1]이다.

여기서 규칙을 볼 수 있는데

N=3의 0번째 index는 55로 N-1인 N=2의 SUM과 동일하다.

N=3의 1번째 index는 45로 N=2의 SUM 빼기 N=2의 0번째 index이다.

이것을 바탕으로 코드를 구현하면 아래와 같은 코드가 나온다.

(다른 블로그에 점화식을 사용한 코드가 있으니 참조)

 

N = int(input())
dp=[1,1,1,1,1,1,1,1,1,1]
tmpdp=[0,0,0,0,0,0,0,0,0,0]
if(N==1):
    print(10)
else:
    for i in range(N-1):
        sumdp=sum(dp)
        tmpdp[0]=sumdp
        tmpdp[1]=tmpdp[0]-dp[0]
        tmpdp[2]=tmpdp[1]-dp[1]
        tmpdp[3]=tmpdp[2]-dp[2]
        tmpdp[4]=tmpdp[3]-dp[3]
        tmpdp[5]=tmpdp[4]-dp[4]
        tmpdp[6]=tmpdp[5]-dp[5]
        tmpdp[7]=tmpdp[6]-dp[6]
        tmpdp[8]=tmpdp[7]-dp[7]
        tmpdp[9]=tmpdp[8]-dp[8]
        dp=tmpdp.copy()
    print(sum(dp)%10007)