[C++] 백준 11057번 : 오르막 수 (S1)

#문제

www.acmicpc.net/problem/11057

11057번: 오르막 수

#풀이 & 학습한 내용

소스코드의 16~22행에 해당하는 Optimal substructure를 통해 for문을 구성합니다. 마지막에 오는 원소가 i일 때 그 직전에 오는 수가 0부터 i까지 가능함을 이용합니다. dp[i][j]를 i번째수가 j일때의 경우의 수라 할때 dp[i][j]는 dp[i-1][0]부터 dp[i-1][j]까지의 합입니다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
long long dp[1002][10];
 
int main(void) {
    int N;
    cin >> N;
 
    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++) {
            dp[i][j] = 0;
            for (int k = 0; k <= j; k++)
                dp[i][j] += dp[i-1][k] % 10007;
        }
    }
    
    long long sum = 0;
    for (int i = 0; i <= 9; i++) {
        sum += dp[N][i];
    }
    cout << sum % 10007 << '\n';
}

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_11057.cpp

HoYoungChun/BOJ_algorithm