[백준/Python] 11057번 오르막 수

오늘 유퀴즈 재방송에서 '인생이 계단이라면 올라가는게 더 힘들까요, 내려가는게 더 힘들까요?'라는 질문이 나왔어요.

여러분의 생각은 어떠신가요?

(항상 문제 제목과 비슷한 뇌절을 치려하는데 버겁네요ㅋㅋㅋㅋㅋ)

 

 

-문제

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

11057번: 오르막 수

 

-풀이 : 동적계획번(DP)를 머릿속에 그려보자

    -문제 받아들이기

수는 0부터 시작할 수 있으며, 다음 자리의 수는 현재 자리의 수보다 크거나 같아야 해요.

input으로 총 자릿수 N이 주어지고 모든 경우의 수를 파악하면 돼요.

 

    -동적계획법으로 구상해보기

dp리스트를 선언해요. 

'dp[N][i] = i로 시작하는 N의 자리 오르막 수의 개수'

 

    -예제 대입해보기

N = 1일 때 

dp[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 인 이유는 1로 시작하는 오르막 수의 개수가 1 하나 인 것처럼 한 자리 밖에 사용하지 못하기 때문이에요.

 

N = 2일 때 

dp[2] = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 인 이유는 첫 자리가 8일 때 88, 89, 99 과 같이 첫 자리 뒤에는 8 이상의 경우의 수가 와야 하기 때문이에요. 

 

    -일반화하기 

dp[N][i] = sum( dp[N-1][i] 부터 dp[N-1][9]까지 )

코드로는 이렇게 짤 수 있습니다.

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

    -개선하기

제가 보여드린 풀이는 이중 리스트를 이용하고, DP 특성상 한번 수정한 원소는 건드리기 않기에 메모리 낭비가 심해요.

그래서 단일 리스트로 아래와 같이 문제를 풀 수 있어요.

 

-소스코드, 개선해버린.

import sys
input = sys.stdin.readline

n = int(input())

dp = [1] * 10

for _  in range(n -1):
    for j in range(10):
        dp[j] = sum(dp[j:]) % 10007
        
print(sum(dp)%10007)