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

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

코드

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

# 초기화
for i in range(10):
    dp[1][i] = 1

# DP
for i in range(2, n+1):
    dp[i][0] = 1
    for j in range(1, 10):
        dp[i][j] = dp[i-1][j]+dp[i][j-1]

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

 

N자리 오르막 수의 개수는 DP를 이용하면 많은 시간을 들이지 않고도 구할 수 있다.

N자리 오르막 수는 (N-1)자리 오르막 수에서 가장 오른쪽의 수와 같거나 그보다 큰 수를 오른쪽에 하나 붙이면 만들 수 있다. 예를 들어, 1234라는 4자리 오르막 수가 있다면 12345와 같이 4와 같거나 그보다 큰 수를 오른쪽에 붙여서 5자리 오르막 수를 만들 수 있다는 것이다.

 

이것을 DP로 구현하기 위해 점화식으로 만들어보면 다음과 같다.

행(i)는 오르막 수의 자릿수, 열(j)는 오르막 수의 가장 오른쪽 수를 말한다.

 

이걸 그대로 코드로 구현해도 문제가 풀어지긴 하지만, 직접 그려보며 더 시간 복잡도가 낮은 방법을 찾을 수 있었다.

 

i>1, j>0일 때, DP[i][j]번째 수는 DP[i][j-1]+DP[i-1][j]와 같다. 이는 DP[i][j-1]이 sum(DP[i-1][:j-1])과 같기 때문이다. 이렇게 구하면 이전 방법에서 DP[i-1][:j+1] 합을 구하던 과정을 없앨 수 있어서 시간 복잡도를 조금 더 작게 만들 수 있다.