[백준 11057] 오르막수_dp(c++)

1.문제

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

11057번: 오르막 수

2.접근방법

1. 이것도 처음에 dfs백트래킹인지 dp인지 헷갈렸음(결국 너무 생각해내기 어려워서 다른 사람들 아이디어 살짝 봤다..)
2. 나의 바로 전에 숫자가 무엇이 오는지에 따라 고를 수 있는 수가 달라짐

 

3.문제풀이

dp[] (행의 인덱스)		dp[][] (열의 인덱스
자리수를 표현		0~9까지의 숫자를 표현

1. n까지의 자리수 중에서 첫번째 자리수는 모든 숫자가 다 배치될 수 있으므로 1로 초기화 시켜준다.
2. 2번째 자리수 부터는 1번째 자리수에서 어떤 숫자가 뽑혔는지에 따라 경우의 수가 달라진다.
3. 2번째 자리수부터 n자리수까지 for문 (첫번째 for문) 을 돌면서 0~9까지의 숫자를 선택하는데 (두번째 for문) 
4. n-1번째 숫자를 j를 골랐다면 n번째 숫자는 j이거나 j이상의 숫자를 뽑아야 한다.(세번째 for문)
5. 결국 n자리번째에 오는 0~9까지 인덱스에는 해당 숫자로 n번째자리를 차지할때의 경우의 수가 카운팅 되어있을 것이다.
6. 출력할때 dp[n][0~9]를 += 해서 값을 출력하면 끝!
7. 참고) 출력할때의 값도 10007로 나눠줘야 하고, dp의 각 합을 구할때에도 10007로 나눈 나머지로 저장해야한다..여기서 시간 잡아먹었다..

 

4.전체코드

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n;
 
int main() {
    cin >> n;
    int** dp = new int*[n + 1];
    memset(dp, 0, sizeof(n + 1));
 
    for (int i = 0; i < n + 1; i++) {
        dp[i] = new int[9];
        memset(dp[i], 0, sizeof(int) * 9);
    }
 
    for (int i = 0; i <= 9; i++) {
        dp[1][i] = 1;
    }
 
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = j; k <= 9; k++) {
                dp[i][j] += dp[i - 1][k];
                dp[i][j] %= 10007;
            }
        }
    }
    int sum = 0;
    for (int i = 0; i <= 9; i++) {
        sum += dp[n][i];
    }
    cout << sum % 10007 << "\n";
    
    return 0;
}