문제

11057번: 오르막 수

풀이

• 왼쪽부터 숫자를 채워 나가기 시작해서 전체 탐색
• 남은 수의 길이 + 방금 채운 숫자일때 오름차순 수 개수를 메모이제이션
• 즉 2자리 남았는데 방금 채운 숫자가 3인경우가 여러번 중복됨
• 이런 경우를 메모이제이션으로 해결하겠다는것

그림 참고

예전에 동아리에서 만들었던 자료

예전에 동아리에서 만들었던 자료

구현

import sys
sys.setrecursionlimit(100000)  # 파이썬 내부적으로 재귀 함수 사용에 제한이 있어 런타임 오류가 발생하는것을 해결

N = int(input())

mem = [[0 for _ in range(10)] for _ in range(N + 1)]

def foo(n, x):
    if n == 0:
        return 0

    if mem[n][x] != 0:
        return mem[n][x]

    summ = 0
    for i in range(x, 10):
        summ += foo(n - 1, i) + 1
    mem[n][x] = summ
    return summ

print((foo(N, 1) + 1) % 10007)

#include <iostream>

using namespace std;

int mem[2000][10] = {0};

int foo(int n, int x) {
    if (n == 0) return 0;

    if (mem[n][x] != 0) return mem[n][x];

    int summ = 0;
    for (int i = x; i < 10; i++) {
        summ += foo(n - 1, i) + 1;
    }
    mem[n][x] = summ;
    return summ;
}

int main() {
    int N;
    cin >> N;
    
    cout << (foo(N, 1) + 1) % 10007;

    return 0;
}