11057_오르막수

▶ 실버 1 (DP)

풀이

규칙이 있을거라고 생각하고 작은 자리수만 적어보았습니다.

# 1 -> 0 1 2 3 4 5 6 7 8 9
# 2 -> 00 / 01 11 / 02 12 22 / 03 13 23 33 / 04 14 24 34 44 / ...
# 3 -> 000 / 001 011 111 / 002 012 112 022 122 222 /
# 4 -> 0000 / 0001 0011 0111 1111
# dp[자리수][끝자리] = dp[자리수][끝자리 - 1] + dp[자리수 - 1][끝자리]

 

적다보니 점화식이 보여서 DP임을 깨달았습니다.

이중 for문을 돌려 (시간 복잡도: O(N), 자리수가 0 ~ 9이므로.)

dp 배열을 채워줍니다.

해당 자리수의 가장 끝자리가 모두 그 전 자리 값들이 누적된 수이므로 답은 dp[N][9]

 

주의 사항

1. 예외처리를 제대로 해줘야합니다.

→ 끝자리가 0인 경우 무조건 0

2. 처음에 착각해서 2차원 배열 초기값으로 [0, 1, 2, ~~, 9] 를 넣었는데, 다시 생각해보니 개수를 넣어줘야 하기 때문에 [1 * 9] 로 넣는 것이 맞습니다.

 

코드

# 11057 오르막수

import sys
input = sys.stdin.readline

n = int(input())

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

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

print(dp[n - 1][9] % 10007)