백준 11057 오르막 수
문제
문제링크 : https://www.acmicpc.net/problem/11057
풀이전략
- 숫자를 0으로 시작할 수 있다는것이 매우 큰 힌트이다.
- 인접한 수가 크거나 같아야한다.
- dp[현재 수][남은 수의 개수]로 메모이제이션을 하여 해결한다.
코드
#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[현재 수][남은 수의 개수]로 알고리즘을 짠 아이디어가 좋았다고 생각한다. 문제를 풀때 항상 base case를 잊지않고 잘 생각해서 짜야한다.
Author And Source
이 문제에 관하여(백준 11057 오르막 수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gomster_96/백준-11057-오르막-수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)