[BOJ] 11057. 오르막 수

Python3,DP

문제

입출력

입출력 예시

주요 포인트

앞자리 수보다 뒷자리 수를 기준으로 잡는 게 포인트이다. 앞자리 수도 물론 규칙이 있긴 하지만 DP로 식을 세우기는 어렵다.

출처: https://jainn.tistory.com/91
+) 사진에 오류 있음
n이 3일 때, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55 가 되는 게 맞음

먼저 n이 1일 때는 모두 하나의 경우의 수를 갖는다.
따라서 dp = [1] * 10을 해준다.

규칙은 항목 전의 끝나는 숫자 경우의 수와 항목 전의 n 경우의 수를 더하는 것이다.
식으로 표현하면,
dp[j] += dp[j-1] 이다.

최종 코드

n = int(input())
dp = [1] * 10

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

print(sum(dp) % 10007)

피드백

끝나는 숫자를 기준으로 경우의 수를 적고, 바로 이전 끝나는 숫자 경우의 수 + 바로 이전 n의 경우의 수를 더한 값이 적힌다는 것을 찾는 게 어려웠다.