[백준 11057] 오르막 수

0. 제목

• 백준 11057 오르막 수
• BOJ 11057 오르막 수
• C++ 11057 오르막 수

---

1. 문제

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

---

2. 풀이

• DP 방식을 이용하였다.
• dp[i][j]는 i단계에서 값이 j일때 오르막 수의 개수를 의미한다.
• 먼저 처음에 1자리 수일 경우에 대한 초기화를 한다. 즉, 1단계일때 오르막 수는 1개씩(0~9) 뿐이다.
• 예를 들어, 5단계에서 값이 7일때 오르막 수의 개수를 구하고 싶다면 5단계의 6일때 오르막 수의 개수와 4단계의 7일때 오르막 수의 개수를 합하면 된다.
• 다음과 같이 써보니 규칙 찾기가 수월하였다.

 

 

---

3. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int N;
    int dp[1001][10];
    cin >> N;
    
    for(int i = 0; i < 10; i++){
        dp[1][i] = 1;   // 한자리 수일 경우에 대한 초기화
    }
    
    for(int i = 2; i <= N; i++){
        dp[i][0] = 1;   //i번째 자리가 0일때는 000.. 이런 형식밖에 없기 때문에 1가지경우
        for(int j = 1; j < 10; j++){
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 10007;
        }
    }
    
    int sum = 0;
    for(int i = 0; i < 10; i++){
        sum += dp[N][i];
    }
    sum %= 10007;
    cout << sum << '\n';
    
    return 0;
}