문제
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수
www.acmicpc.net
풀이
n = 3일때 까지의 예시입니다.
첫번째 열은 1로 초기화를 해줍니다.
두번째 열은 길이가 1인 오르막 수 입니다. 1~9까지 10개가 있습니다.
세번째 열은 길이가 2인 오르막 수 입니다. 예를 들어서,
9x에 들어갈 수 있는 x는 9 1개 입니다. (누적 : 1개)
8x에 들어갈 수 있는 x는 8, 9 2개 입니다. (누적 : 3개)
7x에 들어갈 수 있는 x는 7, 8, 9 3개 입니다. (누적 : 6개)
---
1x에 들어갈 수 있는 x는 1~9 9개 입니다. (누적 : 45개)
0x에 들어갈 수 있는 x는 0~9 10개 입니다. (누적 : 55개)
마지막으로 네번째 열까지 확인해보면 점화식을 유추할 수 있습니다.
네번째 열은 길이가 3인 오르막 수 입니다.
9xx에 들어갈 수 있는 xx는 9x이고, 세번째 열에서 1개 있는 것을 확인했습니다. (누적 : 1개)
8xx에 들어갈 수 있는 xx는 8x, 9x이고, 세번째 열에서 누적 3개 있는 것을 확인할 수 있습니다. (누적 : 4개)
---
1xx에 들어갈 수 있는 xx는 1x~9x이고, 세번째 열에서 누적 45개 있는 것을 확인할 수 있습니다. (누적 : 165개)
0xx에 들어갈 수 있는 xx는 0x~9x이고, 세번째 열에서 누적 55개 있는 것을 확인할 수 있습니다. (누적 : 220개)
따라서 점화식은 dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j-2] ~~~ + dp[i-1][0] 입니다.
오르막 수 개수 (누적)
| 9 시작 | 8 시작 | 7 시작 | 6 시작 | 5 시작 | 4 시작 | 3 시작 | 2 시작 | 1 시작 | 0 시작 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 |
| 1 | 4 | 10 | 20 | 35 | 56 | 84 | 120 | 165 | 220 |
소스 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include<iostream>
using namespace std;
int dp[1002][10];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int i = 0; i < 10; i++)
dp[1][i] = 1;
for (int i = 2; i < 1002; 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 n;
cin >> n;
cout << dp[n + 1][9] << endl;
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 17070] 파이프 옮기기 1 (C++) (0) | 2021.08.23 |
|---|---|
| [백준 14500] 테트로미노 (C++) (0) | 2021.08.21 |
| [백준 17609] 회문 C++ (0) | 2021.08.21 |
| [백준 1756] 피자 굽기 (C++) (0) | 2021.08.19 |
| [백준 5557] 1학년 (C++) (0) | 2021.08.19 |