▶실버1
풀이
처음에는 왜 dp인지 이해가 가지 않음 -> 모든 수를 탐색하며 오르막 수인지 확인하는 작업을 하기엔 시간이 너무 많이 걸리기 때문에 dp로 처리
만약 0_ _이면 한 자리가 추가될 때 0 0 _ _ (1가지) 만 가능
1 _ _이면 0 1 _ _, 1 1 _ _ (2가지) 가능
....
9 _ _이면 0 9 _ _, 1 9 _ _, ~ , 9 9 _ _ (10가지) 가능
이런 식으로 생각하면 자릿수와 맨 앞 자리의 수가 무엇인지를 따져 `dp[i][j] : 맨 앞 자리 수가 j인 i자리의 수의 개수` 로 놓는다.
ex) 3자리 수 오르막 수 구하기
3자리 수의 오르막 수의 개수를 구하기 위해서는 dp[3][0] + dp[3][1] + ... + dp[3][9] 을 구하면 되는데
dp[3][0] = dp[2][0]
dp[3][1] = dp[2][0] + dp[2][1]
...
dp[3][9] = dp[2][0] + dp[2][1] + ... + dp[2][9] 이다.
이런식으로 1자리수부터 n자리수까지의 dp값을 모두 더하면 n자리수의 오르막 수의 개수를 알 수 있다.
이때 기저조건은 dp[1][0 ~ 9] = 1이다.
코드
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int dp[1001][10];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
int sum = 0;
cin >> n;
//한 자리 수에는 모두 1
for (int i = 0; i < 10; i++) {
dp[1][i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 10; j++) {
for (int k = j; k < 10; k++) {
dp[i][j] += dp[i - 1][k];
}
//dp값이 커질 수 있기 때문에 나머지를 저장
dp[i][j] %= 10007;
}
}
for (int i = 0; i < 10; i++) {
sum += dp[n][i];
//문제에서 10007의 나머지가 답이라고 했기 때문에 10007로 나눈 나머지 값이 최종 답
sum %= 10007;
}
cout << sum;
}
'Algorithm > Baekjoon' 카테고리의 다른 글
11660_구간 합 구하기 5 (0) | 2023.01.11 |
---|---|
11055_가장 큰 증가 부분 수열 (0) | 2023.01.10 |
2003_수들의 합 2 (0) | 2023.01.02 |
21921_블로그 (0) | 2023.01.01 |
2583_영역 구하기 (0) | 2022.11.11 |