1562 - 계단 수
본문
$45656$이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 $1$이다. 이런 수를 계단 수라고 한다.
$N$이 주어질 때, 길이가 $N$이면서 $0$부터 $9$까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. $0$으로 시작하는 수는 계단수가 아니다.
입력
첫째 줄에 $N$이 주어진다. $N$은 $1$보다 크거나 같고, $100$보다 작거나 같은 자연수이다.
출력
첫째 줄에 정답을 $1\,000\,000\,000$으로 나눈 나머지를 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
풀이
문제에서 원하는 조건은, ‘계단수’이면서 ‘$0$부터 $9$까지 모든 수가 1번 이상 포함’ 이라는 조건이다. 길이가 9일 때는 만들 수 있는 계단 수가 없다. 길이가 10일 때부터 만들 수 있는 계단 수가 생기기 시작한다. 그렇다고 $N$이 커지면서 그에 따른 규칙이 보이지 않는다. 생각보다 만들 수 있는 방법이 많았기 때문. 9876543210이 고정된 상황에서 출발하는 것으로 생각했는데, 123454567890와 같이 생각보다 예외가 많았다. 사실 위 경우가 수많은 경우 중 하나였던 것. 규칙을 찾는 것은 불가능하다고 판단했다.
그래서 모든 계단 수를 만들어서 그것이 모든 자리수를 포함하는지를 확인하는 것이 좋다고 판단했다. 그런데 길이가 $N$인 수는 총 $10^N$개가 있다. 모든 경우의 수를 세어야하지만 그렇다고 하나하나 만드는 것은 불가능하다. 그러므로 비슷한 경우는 묶어서 하나의 경우로 생각할 수 있는 방법을 찾아야한다.
계단수를 만드려면 현재까지 만든 수의 가장 마지막에 조건에 맞는 숫자를 추가하는 방법을 사용할 수 있다. 각각의 계단수를 모두 저장할 필요 없이 마지막 숫자로만 묶을 수 있다. 그런데 마지막 숫자만 기억한다면 그 계단수가 어떤 숫자들을 사용했는지를 알 수 없다. 그래서, 숫자의 개수도 10개밖에 되지 않으니까, 비트필드를 이용해서 각 수가 어떤 숫자들을 사용하고 있는지를 확인할 수 있도록 하자. 즉 모든 계단수를 마지막 숫자가 무엇인지와 어떤 숫자들을 사용했는지를 기록할 수 있다면 같은 상황끼리 묶어서 결과를 낼 수 있다.
경우의 수를 계산하기 위해 비슷한 경우는 묶고, 그것을 활용하여 다음 경우를 계산하는 방법이므로, dp를 이용하여 구현할 수 있다. dp에서 사용할 state는 2개로, 어떤 숫자들을 사용했는지 나타내기 위한 비트필드 (10자리), 그리고 지금까지 만들어진 수의 마지막 자릿수 (10가지) 이다. 만들어지는 dp배열은 dp[1 << 10][10]이고, 1번당 최대 $2^{10} \times 10 = 10240$번 iteration을 돌게 된다. $N$의 범위가 최대 100까지이므로, 약 100만번의 dp연산으로 경우의 수를 구할 수 있으므로 시간 안에 돌 수 있다고 판단할 수 있다.
계획했으면 실천해보자. 어떤 계단수의 현재 상태를 ‘비트필드 + 마지막 숫자’로 기록하였다면, 거기에 다른 숫자를 붙여 또 다른 계단수를 만드는 방법은 ‘현재의 비트필드 | (이번에 붙인 숫자) + 이번에 붙인 숫자’로 변환된다. 대부분의 경우에서 현재 마지막 숫자보다 $1$ 크거나 작은 수로 계단수를 이을 수 있다. 다만 현재 마지막 숫자가 $0$ 또는 $9$라면 양방향으로 붙일 수는 없다. 그 부분만 핸들링하여 모든 경우의 수를 계산할 수 있다.
다만 경우의 수가 매우 많아지므로 각 dp칸마다 모듈러 연산을 수행해주도록 하자.
- 참고 알고리즘 : 다이나믹 프로그래밍
코드
사용 언어 : C
최종 수정일 : 2023 / 7 / 31
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#define DIGIT 10
const int MOD = (int)(1e9);
int dp[1 << DIGIT][DIGIT];
int batch[1 << DIGIT][DIGIT];
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i < DIGIT; ++i) {
dp[1 << i][i] = 1;
}
long long tempRetval = 0;
for (int t = 2; t <= n; ++t) {
for (int i = 0; i < (1 << DIGIT); ++i) {
for (int j = 0; j < DIGIT; ++j) {
batch[i][j] = dp[i][j];
dp[i][j] = 0;
}
}
for (int i = 0; i < (1 << DIGIT); ++i) {
for (int j = 0; j < DIGIT; ++j) {
if (j > 0) {
dp[i | (1 << (j - 1))][j - 1] += batch[i][j];
dp[i | (1 << (j - 1))][j - 1] %= MOD;
}
if (j < 9) {
dp[i | (1 << (j + 1))][j + 1] += batch[i][j];
dp[i | (1 << (j + 1))][j + 1] %= MOD;
}
}
}
}
int retval = 0;
for (int i = 0; i < DIGIT; ++i) {
retval = (retval + dp[(1 << DIGIT) - 1][i]) % MOD;
}
printf("%d", retval);
return 0;
}