[백준][dp] 11057 오르막수 c++구현

목차

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

문제

 

https://be-senior-developer.tistory.com/22

[백준][dp] 10844 쉬운 계단 수 c++ 구현

 

문제 구현 방향

위의 문제와 굉장히 유사한 문제이다. 오랜만에 풀어서 감이 안잡혀서 위에 문제를 다시 보고 풀었다..

0 ~ 9까지를 따로 배열로 만들고 누적하는 식의 풀이 방법으로 풀어야 한다.

 

 

 

 

문제 풀이

 

0        1        2        3        4        5        6       7        8        9

 

1자리

1

1

1

1

1

1

1

1

1

1

 

2자리

10

9

8

7

6

5

4

3

2

1

 

3자리

55

45

36

28

21

15

10

6

3

1

 

 

규칙이 보인다! 그 전 자리에서 누적한 것을 넣어주면 된다.

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>
#include<stack>

using namespace std;

typedef long long ll;
ll dp[1001][1001] = {0};
int N;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (int i = 0; i <= 9; i++) {
        dp[1][i] = 1;
    }
    cin >> N;
    for (int i = 2; i <= N; i++) {
        int total = 0;
        for (int j = 9; j >= 0; j--) {
            total += (dp[i - 1][j]% 10007);
            dp[i][j] = total;
        }
    }
    int sum = 0;
    for (int i = 9; i >= 0; i--) {
        sum += dp[N][i];
    }
    cout << sum%10007;

    return 0;
}