백준 1562번

오늘 풀어본 문제는 백준의 1562번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

$45656$ 이란 수를 보자.

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

$N$ 이 주어질 때, 길이가 $N$ 이면서 $0$ 부터 $9$ 까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. $0$ 으로 시작하는 수는 계단수가 아니다.

입력

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

출력

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

풀이과정

1번째 시도

이 문제를 해결하기 위해서 사용한 방법은 DP와 비트마스킹이다. 어제 풀었던 외판원 순회 문제처럼 DP 배열에 비트마스킹을 활용하여 상태를 저장해두는 방식이다.

DP 배열은 $3$ 차원 배열로 구성하였으며, 첫 번째 인덱스는 처음 시작한 숫자, 두 번째 인덱스는 현재 몇 개의 숫자를 결정했는지, 그리고 마지막 인덱스는 어떤 종류의 숫자들을 사용했는지 비트마스킹을 이용하여 저장한다.

코드는 다음과 같이 작성하였다.

#define MOD 1000000000
#include <bits/stdc++.h>

using namespace std;

int N;
int dp[10][101][1 << 10] = {0,};

int search(int start, int currentDigit, int bits);

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;

    int result = 0;

    for (int i=1; i<10; i++) {
        result += search(i, 1, 1 << i);
        result %= MOD;
    }

    cout << result;

    return 0;
}

int search(int start, int currentDigit, int bits) {
    if (start < 0 || start > 9) {
        return 0;
    }
    else if (dp[start][currentDigit][bits] != 0) {
        return dp[start][currentDigit][bits];
    }
    else if (currentDigit == N) {
        if (bits == (1 << 10) - 1) {
            return 1;
        }
        else {
            return 0;
        }
    }
    else {
        int result=0;

        result += search(start + 1,
                         currentDigit + 1,
                         bits | 1 << (start + 1));

        result %= MOD;

        result += search(start - 1,
                         currentDigit + 1,
                         bits | 1 << (start - 1));

        result %= MOD;

        dp[start][currentDigit][bits] = result;

        return result;
    }
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

오늘은 한 번에 통과되서 뭔가 신기하다. 지금쯤 시간 초과나 틀렸습니다가 떠서 침대 베개에 얼굴을 파묻고 있을 시간인데 뭔가 블로그 글을 벌써 쓰고있는게 조금 얼떨떨하다… 그래도 잘 풀렸으니 다행이겠지?

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/1562

← Previous Post Next Post →