[Python][백준][11057] 오르막 수 (DP)

🍋 문제링크

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

11057번: 오르막 수

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 123172 KB

시간 : 120 ms

🍉 Code

N = int(input())
dp = [[0 for _  in range(19)] for _ in range(1009)]

dp[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

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

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

🥝 메모

DP[][] 배열을 2차원으로 선언

DP[x][y] → x : 입력으로 주어지는 숫자 ( = 오르막수의 길이 )

                  y : 가장 큰 자리의 숫자 

< 예시 >
000    → dp[3][0]
3367 → dp[4][3]

 

dp[1] 는 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 으로 초기화

위의 그림에 의해, dp[k][0] = dp[k-1][0] + dp[k-1][1] + dp[k-1][2] + ... + dp[k-1][9]

                           dp[k][1] =                       dp[k-1][1] + dp[k-1][2] + ... + dp[k-1][9]

                           dp[k][2] =                                          dp[k-1][2] + ... + dp[k-1][9]

                              . . .

                          dp[k][9] =                                                               ... dp[k-1][9]

라는 규칙을 찾을 수 있으므로

 

j == 0일때는

        dp[i][j] = sum(dp[i-1])

j ≠ 0 일때는

        dp[i][j] = dp[i][j-1] - dp[i-1][j-1]

의 규칙을 얻을 수 있다

 

🍓 참조

< 파이썬 배열의 값 전부 더하기 >

arr = [1, 2, 3, 4, 5] sum(arr)