[알고리즘/백준] 11057번 오르막 수 Python 파이썬

 

아쉽게도 골드 문제는 아니였지만 드디어 DP 문제를 풀이 안보고 풀 수 있게 되었습니다. 

 

 

수의 길이 N이 주어졌을 때 오름차순을 이루는 수%10007 을 구하는 문제였습니다. DP 문제를 풀면서 느낀 점은 규칙성을 찾는 것이 매우 중요하다고 느꼈고 이를 적용시키기 위해서는 직접 몇가지의 경우의 수를 적어보면서 어떻게 결과가 도출되는지 과정을 살펴보는 것이었습니다. 

 

먼저 다음과 같은 코드로 통과하였습니다.

 

import sys
input = sys.stdin.readline

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

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

print(sum(dp)%10007)

 

위 코드에서 i == 2 부분은 따로 처리 안해줘도 되는 것을 나중에 알았습니다.

 

푼 과정은 먼저 스스로 풀기 위해서 30분이라는 제한 시간을 두고 아래와 같이 적으면서 풀이해보았습니다.

 

 

경우의 숫자 경우 N = 1 , N = 2 , N = 3 일 때 정답이 도출되는 과정을 적어보았고 이를 따라가면서 아래와 같은 규칙성을 찾을 수 있었습니다. 풀이하면서 주의할 점은 같은 숫자 묶음(00, 11)도 오르막으로 쳐준다는 점입니다.

 

 

먼저 앞자리에 올 수 있는 숫자들을 배치해놓고 숫자의 길이가 한 자리씩 늘어날 수록 전 자리의 경우의 숫자의 합이 경우의 숫자가 된다는 규칙성을 찾을 수 있었습니다. (0이라면 0~9자리의 경우의 숫자 합이 / 5이라면 5~9자리의 경우의 숫자의 합이)

 

사실 보고 바로 딱 이거다 알기는 어려웠고 어? 이 규칙성인가? 싶어서 해당 규칙을 코드로 짜서 테스트케이스를 테스트해보니 맞는 것을 깨달을 수 있었던 것 같습니다. 이렇게 차근차근 감을 익히는 게 중요한 거 같습니다.

 

한동안은 DP 문제를 연습할 것 같습니다.