Memo
로직 설명
•
문자열의 인덱스를 0 부터 N - 1까지 증가시켜 갑니다. (실제로는 문자열을 쓰지 않음)
•
다음 인덱스와 값을 정해주고 재귀적으로 함수를 호출합니다.
•
base case
→ 인덱스가 N - 1일 때 value ~ 9 사이의 갯수를 리턴합니다.
→ dp[index][value]의 값이 있으면, 그대로 사용합니다.
•
같은 인덱스 일 때, value 값을 9 부터 value 까지 감소시키면서 누적 합을 dp[index][value]값에 저장해 줍니다.
value == 이전 함수 호출에서 정해준 값
자료 구조
•
dp[1002][11]
행 → 몇 번째 인덱스에서
열 → 0 ~ 9 값일 때
현재 행 보다 큰 값, 열 보다 큰 값들의 누적 합 저장
코드 설명
•
int logic(int index, int value)
index → 몇 번째 인덱스 ( ex > 123 에서 2는 1번째 인덱스)
value → 이전 함수 호출에서 정해준 값 (이전 함수에서의 value값 보다 크거나 같은 수)
Code
제출 날짜
@4/6/2021
메모리
2060 KB
시간
0 ms
#include <iostream>
int N;
int dp[1002][11];
int ans;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
input_faster();
std::cin >> N;
}
int logic(int index, int value)
{
if (dp[index][value])
return (dp[index][value]);
int cnt = 0;
if (index == N - 1) // last
return (10 - value);
for (int i = 9 ; i >= value ; i--)
{
cnt += logic(index + 1, i);
if (cnt >= 10007)
cnt %= 10007;
dp[index][i] = cnt; // dp 업데이트
}
return (cnt);
}
void solve()
{
ans = logic(0, 0) % 10007;
}
void print_val()
{
std::cout << ans;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사
