[백준 11057] 오르막 수 (DP) (C++) - S1
문제
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수
www.acmicpc.net
풀이
문제를 처음 보았을 때 dp로 풀어야겠다고 바로 생각이 든 문제이다.
dp로 접근은 했지만, 점화식을 찾는 과정에서 시간이 오래 걸렸다.
일단, 2차원 dp 배열을 선언했다.
dp[i][j] : 길이가 i 이면서, j 라는 숫자로 끝나는 수
ex) dp[2][3] : 길이가 2이면서, 3으로 끝나는 수 -> 03, 13, 23, 33
일단, 길이가 1인 경우에는 숫자가 1개이므로, 끝자리 수가 0 ~ 9일 때 모두 1개이다.
즉, dp[1][0] = dp[1][1] = ... = dp[1][9] = 1 이다.
이제는 점화식을 찾아낼 차례였다.
길이가 i 이면서 j 라는 숫자로 끝나는 수(dp[i][j])는, 길이가 i - 1이면서 마지막 수가 j 이하인 수(dp[i - 1][k], 0 <= k <= j)의 마지막에 j만 추가해준 형태이다.
쉽게 예를 들어 설명해보도록 하겠다.길이가 3이면서 4라는 숫자로 끝나는 수를 생각해보자.
이는 dp[3][4]로 표현할 수 있다.
이에 해당되는 수는 004, 014, 024, 034, 044, 114, 124, 134, 144, 224, 234, 244, 334, 344, 444, 총 15개가 있다.
즉, dp[3][4] = 15 이다.
(마지막에 4 추가)
길이가 2이면서 0으로 끝나는 수 : 00 -> 004
길이가 2이면서 1으로 끝나는 수 : 01, 11 -> 014, 114
길이가 2이면서 2로 끝나는 수 : 02, 12, 22 -> 024, 124, 224
길이가 2이면서 3으로 끝나는 수 : 03, 13, 23, 33 -> 034, 134, 234, 334
길이가 2이면서 4로 끝나는 수 : 04, 14, 24, 34, 44 -> 044, 144, 244, 344, 444
이 과정을 통해, 길이가 3이면서 4로 끝나는 수는 위와 같은 방식으로 만들 수 있는 것이다.
식으로 나타내면, dp[3][4] = dp[2][0] + dp[2][1] + dp[2][2] + dp[2][3] + dp[2][4] 이다.
즉, 반복문을 사용하여 dp[i][j] += dp[i - 1][k] (0 <= k <= j) 식을 구현하면 된다.
최종적으로, 길이가 N인 오르막수의 개수는 dp[N][0] 부터 dp[N][9]까지 합한 개수이다.
코드
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <sstream>
#include <cstdio>
#include <cmath>
using namespace std;
using ll = long long;
int dp[1001][10];
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
for (int i = 0; i < 10; i++)
dp[1][i] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 10; j++)
for (int k = 0; k <= j; k++) {
dp[i][j] += dp[i - 1][k];
dp[i][j] %= 10007;
}
}
int ans = 0;
for (int i = 0; i < 10; i++) {
ans += dp[n][i];
ans %= 10007;
}
cout << ans;
return 0;
}