[Python/파이썬 11057 백준] 오르막 수 (다이나믹 프로그래밍)

 

www.acmicpc.net/problem/11057

11057번: 오르막 수

풀이

10844 쉬운 계단수 문제랑 굉장히 유사한 문제입니다..

유사한 문제 풀어보면 쉽게 풀리네용...

 

주의할 점은 첫번째 0인 숫자가 들어갈 수 있다는거구, 오름차순 숫자 갯수를 찾아야합니다.

또한 이차원 리스트 사용

 

숫자를 일일히 구하다보면 공통점이 있는데

마지막 수가 0일 경우 다음 숫자는 1~9가 가능하고

1일 경우 2~9

2일 경우 3~9

.

.

.

9는 다음 숫자가 들어올 수 없어서 dp로 따지게 되면 전에 해당하는 값을 유지시켜줍니다.

# 오르막수 오름차순인 수를 구하는 문제
# 주의 첫번째 수가 0도 들어갈 수 있음
# 10844 쉬운 계단수랑 유사한 문제
# 이 문제는 0일때 1~9 ,1일때 2~9, 2일때 3~9 ....... 9는 그냥 전에꺼랑 같도록

import sys
input=sys.stdin.readline

n= int(input())
dp=[[0]*10 for i in range(n+1)]

for i in range(10):
    dp[1][i]=1
    
for i in range(2,n+1):
    for j in range(10):
        if j==9:
            dp[i][j]=dp[i-1][j]
        else:
            for k in range(10):
                if k<j:
                    continue
                dp[i][j]+=dp[i-1][k] 

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

 

 

이 문제도 풀어보세요

금방 풀릴겁니당..

www.acmicpc.net/problem/10844

 

10844번: 쉬운 계단 수