白駿11057上り坂
質問する
質問リンク:https://www.acmicpc.net/problem/11057
ポリシー
コード#コード#
#include<bits/stdc++.h>
using namespace std;
#define mine
int N;
int dp[11][1002];
const int MOD = 10007;
int incNum(int n, int c){
if(c <= 0) return 0;
/// 숫자가 하나 남았을 때는 자명하므로 미리 선언해준다.
if(c == 1) return dp[n][1];
int& ret = dp[n][c];
if(ret != -1) return ret;
ret = 0;
// 다음재귀에서 사용할 수 있는 모든 수를 계산해준다.
for(int i=n; i<10; i++){
ret = (ret+incNum(i, c-1))%MOD;
}
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
// freopen("../input.txt","rt",stdin);
cin >> N;
memset(dp, -1, sizeof(dp));
// 남은수의 개수가 1일경우의 값들을 미리 초기화해준다.
for(int i=0; i<10; i++) dp[i][1] = 10-i;
// 처음숫자가 0으로 시작하면 모든 수가 가능하므로 0으로 시작한다.
cout << incNum(0, N) << endl;
return 0;
}
感想
dp[現在数][残数]でアルゴリズムを記述する考えがよいと思います.問題を解くときはbasecaseを忘れずによく考えてから編みます.
Reference
この問題について(白駿11057上り坂), 我々は、より多くの情報をここで見つけました https://velog.io/@gomster_96/백준-11057-오르막-수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol