문제
풀이
•
왼쪽부터 숫자를 채워 나가기 시작해서 전체 탐색
•
남은 수의 길이 + 방금 채운 숫자일때 오름차순 수 개수를 메모이제이션
•
즉 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)
Python
복사
#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;
}
C++
복사
