[백준]11057.오르막수

문제 설명

수의 자리수가 주어졌을 때 그 자리수의 모든 수 집합에 대해 오르막수의 갯수를 모두 구하라!

오르막수는 왼쪽에서 오른쪽으로 자리수가 이동할 때마다 해당 자리수의 값이 점점 더 커지거나 같아야 한다. 첫자리에 0이 들어올 수 있다.

예를 들어 자리수가 2라하면 00에서 부터 시작하여 99까지의 수를 확인하여 오르막수의 갯수를 구하면 된다.

01인 경우 증가하므로 오르막수, 00또한 값이 첫번째 두번째 자리수의 값이 동일하므로 오르막수라 말할 수 있다. 21은 안됨!

문제 접근

• 오르막수를 수학적으로 정의해보자

  i는 자리 위치 (맨 왼쪽이 1이고 오른쪽으로 이동하며 1씩 증가한다.) x_i는 i번째 자리의 수라 한다면

  x_i <= x_{i+1}

  이란 식이 성립해야 한다.

  이를 보면 오르막 수를 판단하기 위해선 바로 직전의 값만 비교해보면 된다는 뜻!

• dp로 접근하자

  단계는 자리 위치

  최적값은 오르막수의 갯수

  변수는, 오르막수의 갯수가 해당 자리 위치의 수 에 영향 받으므로 수라고 볼 수 있다. 0~9까지의 수

  순환식을 구해보면,

  이전 단계의 0은 0으로 갈 수밖에 없고,

  이전 단계의 0,1은 1로 갈 수 밖에 없다.

  따라서 n번째 스텝의 수 i의 오르막수의 갯수는 n-1번째 스텝의 수0i 의 오르막수 갯수를 모두 더한 것과 같다 말할 수 있다. 이는 완전탐색 접근으로써 최적 해일 수 밖에 없다. 따라서 n번째 스텝의 구하고자하는 해는 n번째 스텝에서 09까지의 경우를 모두 합한 것과 같다.

  자세한 수식은 이미지의 두번째 페이지에 있다.

구현

n = int(input())

dp = [[0 for _ in range(10)] for _ in range(n+1)] # 편의를 위해 1번째 인덱스부터 고려하기.

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

for step in range(1,n+1):
    dp[step][0] = 1
    for k in range(1,10):
        dp[step][k] = (dp[step][k-1]%10007 + dp[step-1][k]%10007)%10007

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