백준 11057 오르막 수

문제

문제링크 : https://www.acmicpc.net/problem/11057

풀이전략

1. 숫자를 0으로 시작할 수 있다는것이 매우 큰 힌트이다.
2. 인접한 수가 크거나 같아야한다.
3. 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를 잊지않고 잘 생각해서 짜야한다.