https://www.acmicpc.net/problem/11057
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 끝자리를 기준으로 행렬을 만들어 표현하여 규칙을 찾는다면 쉽게 해결할 수 있는 문제였습니다.
다음의 표를 기준으로 설명하겠습니다. 각각 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 끝나는 경우를 n이 1일 때, 2일 때, 3일 때로 구분한 것입니다.
위의 표를 보시면 쉽게 알 수 있는데 바로 arr[i][j] = arr[i-1][j] + arr[i][j-1]입니다. 따라서 이를 소스코드에 적용하면 다음과 같습니다.
소스코드 - python
|
1
2
3
4
5
6
7
8
9
|
n = int(input())
dp = [[1] * 10 for _ in range(n)]
for i in range(1, n):
for j in range(1, 10):
dp[i][j] = (dp[i][j-1] + dp[i-1][j])%10007
print(sum(dp[n-1])%10007)
|
cs |
소스코드 - c++
|
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
|
#include <bits/stdc++.h>
#define MAX 1001
#define MOD 10007
using namespace std;
int main(void) {
int n;
int result = 0;
scanf("%d", &n);
int dp[MAX][10];
fill(&dp[0][0], &dp[MAX-1][10], 1); // 배열 전체 1로 초기화
for (int i = 1; i < n; i++) {
for (int j = 1; j < 10; j++)
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD;
}
for (int i = 0; i < 10; i++) {
result += dp[n - 1][i];
}
printf("%d", result%MOD);
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 9461번: 파도반 수열(Python) (0) | 2022.01.31 |
|---|---|
| 백준 알고리즘 2193번: 이친수(Python) (0) | 2022.01.31 |
| 백준 알고리즘 9251번: LCS(Python) (0) | 2022.01.29 |
| 백준 알고리즘 1904번: 01타일(Python) (0) | 2022.01.28 |
| 백준 알고리즘 2156번: 포도주 시식(Python) (0) | 2022.01.25 |