[DP] 백준 11057 파이썬 (오르막 수) 실버1

-풀이

n=int(input())
dp=[1]*10
for i in range(n-1):
  for j in range(1,10):
    dp[j] += dp[j-1]
print(sum(dp)%10007)

-풀이 설명

[20~25분 no sol] 표를 그려서 규칙은 찾았는데 점화식을 세울 방법을 몰랐다. 내가 사고한 방식의 문제점은 타일링 문제처럼 dp리스트에 예제 출력값을 그대로 넣으면서 생각한 게 잘못 생각한 것이었다. 끝자리가 0~9일 때 올 수 있는 개수를 dp에 넣어서 규칙을 찾아주면 되었다.

 

출처 : https://jainn.tistory.com/m/91

위와 같이 dp[j] += num[j-1] 이라는 규칙이 보인다.

따라서 끝까지 적용해주면 된다.