BOJ 백준 11057: 오르막 수

Table of contents

들어가며

걸린 시간: 39분

이 문제는 완탐으로 풀려고 하면요.
무려 $10^{1000}$ 이라는 미친 가짓수가 나와서, 완탐으로는 못 풀어서 딴 풀이를 생각해야 합니다.

접근

그래서 저는 DP를 의심했습니다.
왜냐면, 일일히 가짓수를 세보는데 전에 세었던 가짓수가 필요하더라고요.

구현

점화식을 세우니 확실히 구현이 편하네요.
점화식을 거의 그대로 쓰면 되니깐요. 🥸 앞으로 DP가 의심되는 상황이면 키보드에 손을 올리기 보다는, 점화식을 세워야 겠습니다!

import sys

input = sys.stdin.readline


if __name__ == "__main__":
    MOD = 10_007
    N = int(input().strip())
    dp = [[0 for __ in range(10)] for _ in range(N + 1)]
    for i in range(10):
        dp[1][i] = 1

    if N <= 1:
        print(sum(dp[N]))
        exit(0)
    for i in range(10):
        dp[2][i] = 10 - i

    for i in range(3, N + 1):
        for j in range(10):
            for k in range(j, 10):
                # 길이가 i이고, 첫 숫자가 j인 오름수의 개수는
                # 길이가 지금 거보다 하나작고, 첫 숫자가 j보다 크거나 같은 오름수들의 합이다.
                dp[i][j] += dp[i - 1][k] % MOD
                dp[i][j] %= MOD
    ret = 0
    for n in dp[N]:
        ret += n % MOD
    print(ret % MOD)

다른 풀이

DFS와 cache 데코레이터를 이용해서 풀었습니다.

import sys
from functools import cache

sys.setrecursionlimit(10**6)
input = sys.stdin.readline


@cache
def dfs(n, k):
    if n == 1:
        return 1
    tmp_sum = 0
    for i in range(k, 10):
        tmp_sum += dfs(n - 1, i) % MOD
        tmp_sum %= MOD
    return tmp_sum % MOD


if __name__ == "__main__":
    MOD = 10_007
    N = int(input().strip())
    ans = 0
    for i in range(10):
        ans += dfs(N, i)
        ans %= MOD
    print(ans % MOD)