[BOJ] 백준 11057번: 오르막 수

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

11057번: 오르막 수

 

백준 10844번: 쉬운 계단수와 유사한 문제입니다.

 

#include <bits/stdc++.h>
using namespace std;

const int MOD = 10007;
int N, res, dp[1001][10];

void solve(){
	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 = 0; k <= j; ++k){
				dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;
			}
		}
	}
	
	res = 0;
	for(int i = 0; i <= 9; ++i){
		res = (res + dp[N][i]) % MOD;
	}
	cout << res; 
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	
	solve();
}

 

dp 문제는 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이합니다.

 

1) table 정의

dp[i][j] : 숫자 j로 끝나는 길이가 i인 오르막 수의 개수(j = 0, 1, 2, ... , 9)

 

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][j] + dp[i-1][k]) % MOD;
        }
    }
}

숫자 j로 끝나는 길이가 i인 오르막 수의 개수

= 숫자 j보다 작거나 같은 수 k로 끝나는 길이가 (i-1)인 오르막 수의 개수의 합

 

3) 초기값 설정

dp[1][0~9] = 1;

 

 

10844번 문제와 마찬가지로 2차원 배열을 사용함으로써 case를 분류해 문제를 쉽게 해결할 수 있습니다.

나머지 연산에 주의해 주세요.

 

시간복잡도는 O(N)입니다.