백준, BOJ, 11057번, 오르막 수 : C++ [CPP]

DP 중에서 하다보면 규칙을 찾는 것이다.

규칙을 2분만에 찾아서 바로 풀 수 있었다.

하지만 잘 보이지 않는다면.. 조금 힘들다.

 

항상 N-1과 N의 관계를 생각하면 될 것 같다.

 

 

https://www.acmicpc.net/problem/11057

 

---

#맞는 풀이

#include <iostream>

using namespace std;

int dp[1001][10];

int N;

int main(){
    cin >> N;
    
    //초기값
    for(int i = 0; i<=9; i++){
        dp[1][i] = 1;
    }
    
    // ex) dp[4][2] 는 dp[3][0] + dp[3][1] + dp[3][2] 이다.
    // 3까지 0이었다면 2를 선택할 수 있고 3까지 1이었다면 2를 선택할 수 있고...
    // 3까지 3이라면 2는 선택을 못하므로 제외
    for(int i=2; i<=N; i++){
        for(int j = 0; j<=9; j++){
            for(int k = 0; k<=j; k++){
                dp[i][j] += dp[i-1][k];
                dp[i][j] %= 10007;
            }
        }
    }
    
    //N에서 모든 개수는 0으로 끝나는 것부터 9로 끝나는 것 모두 합치면 된다.
    int ans = 0;
    for(int i =0; i<=9; i++){
        ans += dp[N][i];
        ans %= 10007;
    }
    
    cout << ans;
}

 

코멘트로 달아놨다.