https://www.acmicpc.net/problem/11057
오르막 수는 N이 1,000이므로, 모든 경우의 수를 구하는 경우 시간 초과가 발생합니다.
오르막 수는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다.
먼저, 테이블 d[i][j]는 길이가 N이고, i로 끝나는 오르막 수의 개수로 정의했습니다.
초기값 d[0][1] ~ d[9][1]은 모두 1입니다.
또한, d[i][j]는 길이가 N - 1이고, j보다 작거나 같은 오르막 수의 합으로 나타낼 수 있습니다.
아래는 Bottom-Up 방식의 다이나믹 프로그래밍 코드입니다.
#include <bits/stdc++.h>
using namespace std;
#define MOD 10007
int d[10][1010]; // d[i][j]는 길이가 N이고, i로 끝나는 오르막 수의 개수
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
for(int i = 0; i < 10; i++) d[i][1] = 1; // 초기값 지정
for(int i = 2; i <= n; i++){ // 테이블 채우기
for(int j = 0; j < 10; j++){
for(int k = j; k >= 0; k--)
d[j][i] += d[k][i - 1] % MOD; // d[j][i]는 길이가 N - 1이고, j보다 작거나 같은 오르막 개수의 합
d[j][i] %= MOD;
}
}
int ans = 0;
for(int j = 0; j < 10; j++) ans += d[j][n] % MOD; // 길이가 N이고, j로 끝나는 오르막 수의 총합
cout << ans % MOD << "\n";
}
'Algorithm > Dynamic Programming' 카테고리의 다른 글
[백준 12865번] 평범한 배낭 (C++) (0) | 2022.05.09 |
---|---|
[백준 4883번] 삼각 그래프 (C++) (0) | 2022.05.06 |
[백준 9465번] 스티커 (C++) (0) | 2022.05.05 |
[백준 11052번] 카드 구매하기 (C++) (0) | 2022.05.05 |
[백준 2302번] 극장 좌석 (C++) (0) | 2022.05.05 |