[백준] 1562번 C/C++ 풀이 _ 계단수

출처 : https://www.acmicpc.net/problem/1562

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1890	876	610	46.073%

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

그럼, 오늘도 역시 세준이는 0부터 9까지 모든 한 자리수가 자리수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개 있는 지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력

예제 출력

힌트

참고로, N=1일때부터, N=40일 때 까지 답을 모두 더하면 126461847755이 나온다.

출처

문제를 번역한 사람: baekjoon

알고리즘 분류

다이나믹 프로그래밍

>> 풀이 방법

이 문제는 처음에 dfs 로 생각했었는데, 깊이가 깊어질수록 거의 2배씩 증가하는데 깊이가 최대 100이라서, 2¹⁰⁰으로 무조건 시간 초과가 예상되어 다른 풀이를 생각했다.

하지만, 생각에 실패했고 답안을 보게 되었다.

이 문제의 풀이는 dfs와 메모이제이션을 이용한 풀이, for문을 이용하여 bfs 방식으로 푸는 풀이 로 크게 2개가 있는 것 같다.

공통적으로는 0~9 까지의 숫자를 2진수를 이용하여, 표현하는 방법을 사용한다.
2진수에서 0~9 의 숫자를 사용했으면 1로 표시하고, 아니면 0으로 표시한다.

아래와 같은 방식으로 숫자를 표시하는 것이다.

9	8	7	6	5	4	3	2	1	0
1	1	1	1	1	1	1	1	1	1

이럴 경우에 배열을 선언할 때, 1 << 10 = 2¹⁰ =1024개 만큼의 크기가 더 필요하다.
만약, int를 사용했다면 10자리가 모두 1이려면 10억개이기 때문에 너무 많다.

숫자를 지나면 | 연산을 이용하여 1로 변경시켜준다.
그리고 모든 숫자를 지났는지 여부는, 마지막 깊이에서 모든 숫자가 1인 경우 = 1023 일 경우이고, 나머지 경우는 하나라도 거치지 않은 것이다.

아래와 같은 형태이다.

배열[높이][현재 자리수의 숫자][사용한 숫자 체크]

소스코드는 다른 블로그에 있는 타인의 풀이를 참고하였다.

for문을 이용하여 bfs 방식으로 푸는 풀이 는 아래와 같다.

시간 복잡도는 O(n*10*2¹⁰) 이다.

- 깊이는 앞에서부터 시작하는 자리수라고 볼 수 있다.

12라인 : 모든 숫자를 지나는 숫자 1023 을 생성한다.(1111111111)
14라인 : 0을 제외한 1~9까지를 1로 초기화한다. 0은 시작 숫자가 될 수 없기 때문에 제거한다.
16~30라인 : for문을 통하여 높이 2부터 전부 탐색한다.
0000000000 ~ 1111111111 까지의 모든 이전 단계의 숫자사용 여부를 기준으로 다음 단계의 가능한 다음 단계로 넘겨준다.
0 과 9가 아닐 경우에는 하나씩, 현재 자리수 +1, -1 을 한 이전 높이의 두 개를 수행한다.
최외곽의 for문 변수가 하나씩 증가할때마다 깊이가 증가하기 때문에, bfs와 유사한 구조이다.
32라인 : 높이가 n이면서 3번째 요소가 1023인 배열들의 값을 가져와서,정답을 추출한다.

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
#include <stdio.h>
using namespace std;
 
#define mod 1000000000
 
int n, i, j, k, ans;
int dp[101][10][1 << 10];
 
int main() {
    scanf("%d", &n);
 
    int full = (1 << 10) - 1;
 
    for (j = 1; j <= 9; ++j)
        dp[1][j][1 << j] = 1;
 
    for (i = 2; i <= n; ++i) {
        for (j = 0; j <= 9; ++j) {
            for (k = 0; k <= full; ++k) {
                if (j == 0)
                    dp[i][0][k | (1 << 0)] = (dp[i][0][k | (1 << 0)] + dp[i - 1][1][k]) % mod;
                else if (j == 9)
                    dp[i][9][k | (1 << 9)] = (dp[i][9][k | (1 << 9)] + dp[i - 1][8][k]) % mod;
                else {
                    dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j - 1][k]) % mod;
                    dp[i][j][k | (1 << j)] = (dp[i][j][k | (1 << j)] + dp[i - 1][j + 1][k]) % mod;
                }
            }
        }
    }
 
    for (j = 0; j <= 9; ++j)
        ans = (ans + dp[n][j][full]) % mod;
 
    printf("%d", ans);
 
    return 0;
}
Colored by Color Scripter
cs

dfs와 메모이제이션을 이용한 풀이 는 아래와 같다.

메모이제이션을 쓰지 않으면 예상과 같이 너무 느리게 답이 나와서 사용할 수 없다.
5라인과 10라인에서 number를 이용해서 측정해본 결과 메모이제이션을 사용하면,
n이 100이 되더라도 70만 정도이기 때문에 풀이에는 지장이 없었다.
시간 복잡도는 메모이제이션이기 때문에 정확히 구하는 방법을 잘 모르겠다.

11라인 : 해당 위치에서 이전에 구해 놓은 값이 있으면 바로 사용한다.
13라인 : 높이가 n 일 때, 모든 숫자를 사용했으면 (1023, 1111111111 이라면 ) 1로 값을 넣어주고, 아니면 0을 넣는다.
17~20라인 : 현재 높이에서 자리수를 확인하고 다음 단계로 넘어간다.
22라인 : 현재 위치의 값을 구했으면, 메모리에 넣고 함수로 리턴해줘서 다른 재귀함수에서 사용할 수 있게 한다.

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
#include<iostream>
using namespace std;
#define MOD 1000000000
 
long long number = 0 ;
int dp[105][10][1 << 10], n, ans;
 
int dfs(int idx, int num, int bit)
{
    number++;
    if (dp[idx][num][bit])
        return dp[idx][num][bit];
    if (idx == n){
        return bit == (1 << 10) - 1 ? 1 : 0;
    }
    int res = 0;
    if (num + 1 < 10)
        res += dfs(idx + 1, num + 1, bit | 1 << (num + 1));
    if (num - 1 >= 0)
        res += dfs(idx + 1, num - 1, bit | 1 << (num - 1));
    
    return dp[idx][num][bit] = res %= MOD;
}
 
int main()
{
    cin >> n;
    for (int i = 1; i < 10; i++)
    {
        ans += dfs(1, i, 1 << i);
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}
 
Colored by Color Scripter
cs