이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 23 번째 글 입니다.
목차
실버1: 동적 계획 법을 사용하는 문제이다.
대표적인 동적계획법 문제이다. 기초적인 동적 계획법 문제를 풀 때에는 펜을 갖고 쓰는 것이 중요해보인다. 기본적으로 점화식을 갖고 해결하는 방식이기 때문에, 수열 문제를 푸는 것도 같은 사고로 접근해야 한다. 수열 문제가 눈에 들어오지 않으면 쓰면서 규칙을 찾아내듯, 이것도 손아프다고 징징대지말고 쓰면서 찬찬히 푸는 것이 문제를 가장 효과적이고 간결하게 풀 수 있는 방법이다.
N : 1, N : 2
| 숫자 | 오르막 수 개수 | 숫자 | 오르막 수 개수 |
|---|---|---|---|
| 0 | 1 | 공란 | 공란 |
| 1 | 1 | 10~19 | 1~9 : 9 |
| 2 | 1 | 20~29 | 2~9 : 8 |
| 3 | 1 | 30~39 | 3~9 : 7 |
| 4 | 1 | 40~49 | 4~9 : 6 |
| 5 | 1 | 50~59 | 5~9 : 5 |
| 6 | 1 | 60~69 | 6~9 : 4 |
| 7 | 1 | 70~79 | 7~9 : 3 |
| 8 | 1 | 80~89 | 8~9 : 2 |
| 9 | 1 | 90~99 | 9~9 : 1 |
규칙을 보게 되면, 최고 자리 수가 어떤 수이냐에 따라 그 다음 자리수는 결정이 되게 된다. 그런데 여기서 잘 보면, N : 2일 때, 최고자리수가 1인 경우, 오르막 수의 개수는 1의 자리 숫자가 1~9까지 오는 경우가 모두 오르막 수가 될 수 있다.
추가적으로 최고자리수가 2인 경우는, 일의 자리 숫자가 2인 경우부터 발생하는 모든 오르막 수를 더함으로서 만들어진다.
이 규칙을 자세히 보면, 변화하는 파라미터는 총 두개이다.
- 최고자리의 수
- 최고자리에 위치하는 숫자
이 두가지 특징을 가지고 dp를 정의하고, 점화식을 세워보자.
dp[N][m] = N 자리수를 가지는 수가 M의 숫자를 가질 때 가질 수 있는 오르막 수의 개수
dpdp[N] = N 자리수를 가지는 수가 가질 수 있는 오르막 수의 개수
이렇게 정의했을 때, dp 점화식의 정의는 다음과 같다.
\[dp[N][M] = \sum_{i=M}^{9}dp[N-1][i]\]이걸 가지고 dpdp 점화식을 세우면 다음과 같다.
\[dpdp[N] = \sum_{i=0}^{9}dp[N][i] + dpdp[N-1]\]수식도 세웠으니 이제 구현만 하면 된다. 이때, dp를 수행하기 위해서는 초기값을 설정해 줘야 하는데, 이 경우에는 N : 1 인 경우에 해당하는 모든 숫자에 1의 값을 준 뒤에 시작해야 한다.
Code
// 백준 11057번 오르막 수
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N = 0;
int dp[1001][10] = {0};
int dpdp[1001] = {0};
int mod = 10007;
int main(){
cin >> N;
// 초기값 세팅
for (int i = 0; i < 10; i++) {
dp[1][i] = 1;
}
dpdp[1] = 10;
for (int i = 2; i <= N ; i++) {
// dp[N][M]을 구하는 코드
for (int j = 1; j < 10; j++) {
for (int k = j; k < 10; k++) {
dp[i][j] += dp[i-1][k];
dp[i][j] %= mod;
}
}
// dpdp[N]을 구하는 코드
for (int j = 0; j < 10; j++) {
dpdp[i] += dp[i][j];
}
dpdp[i] += dpdp[i-1];
dpdp[i] %= mod;
}
// 정답
cout << dpdp[N] << '\n';
}