계단 수

백준 1562

GOLD I

문제 내용
해결 방안
풀이 코드

문제 내용

문제 링크

해결 방안

N자리 자연수에 대해 모든 자리의 수가 인접한 자리와 1씩 차이나면서, N자리의 숫자 중 0부터 9까지의 수가 모두 나오는 수의 총 개수를 찾는 문제이다.

N의 범위가 100 이하의 자연수이므로, 당연하게도 최대 1e+100이나 되는 모든 수를 전수조사하는 것을 불가능하다. 각 자리의 수를 모두 저장할 필요가 없으므로, 인접한 수에 대해서만 확인하면 된다. 임의의 자리 수에 대해 다음 자리 수가 1만큼 차이나면, 당연하게도 다음 자리 수의 기준에서는 이전 수가 1만큼 차이가 난다. 정리하면, 모든 자리 수를 일일이 기록하는 대신 이전 자리 수와 1만큼 차이가 나는 지만 판별하면 되는 것이다.

위의 방식은 계단 수를 찾는 방법이지만, 문제에서 찾아야 하는 수는 N자리 안에서 0부터 9까지의 모든 수가 등장하는 계단 수이다. 다시 말해, 각 분기별로 0부터 9까지가 모두 등장했는 지를 판별해야 한다는 뜻이다. 0부터 9까지의 수를 bool 자료형의 배열로 나타내는 방법도 있겠지만, 이번 문제에서는 보다 쉬운 방법인 비트마스킹을 이용하는 방법을 사용하고자 한다. i를 0~9 사이의 정수라고 할 때, 2^10 = 1024의 범위 내에서 2^i번째 비트로 각 수가 등장했는 지에 대한 정보를 전달할 수 있다.

위의 세 가지 정보를 바탕으로 바텀 업 방식의 다이나믹 프로그래밍으로 문제를 해결할 수 있다. 다이나믹 프로그래밍을 위해 사용하게 될 위의 세 가지 정보를 정리하면 다음과 같다.

현재 몇 번째 자리의 숫자인가?
이전 자리에서 어떤 숫자가 나왔는가?
현재 자리까지 0부터 9까지의 수 중 어떤 숫자들이 등장했는가?

1번째 자리부터 N번째 자리까지 탐색하면서 이전 자리에서 나온 숫자가 현재의 숫자와 1만큼 차이나면, 그 개수를 합산하고 현재 나온 수를 기록하면 되는 것이다. 다르게 말하면, 존재할 수 있는 각 계단 수의 분기 중 조건에 부합하는 것들의 개수를 각 분기마다 합산하는 것이다. 결론적으로, N번째 자리에서 모든 숫자가 나온 수들에 대해 끝 자리가 0~9인 모든 분기를 합치면 찾고자 하는 답이 나온다.

비트마스킹(Bit Masking)이란?

컴퓨터 과학에서 하나 이상의 인접 비트로 구성된 자료 구조를 비트 필드(bit field)라고 부른다. 흔히 말하는 0과 1로 구성된 비트들로 나타내어지는 형태로, 작업 결과를 표시하거나 컴퓨터 메모리 주소를 저장하는 등 다양한 목적으로 사용될 수 있다. 이러한 비트 필드에서 비트 연산 등을 위해 사용하는 데이터를 비트마스크(bit mask)라고 부른다. 또한, 비트 연산을 위해 비트마스크를 활용하는 방식을 비트마스킹(bit masking)이라고 한다.

프로그래밍 문제 풀이에 있어 비트마스킹은 임의의 수와 그 비트에 관한 문제가 나왔을 때에 사용될 수 있지만, 다른 방식으로는 비트필드를 활용한 다이나믹 프로그래밍이 있다. 비트가 0과 1로 boolean처럼 참과 거짓 2개의 값만 나타낼 수 있는 점을 활용한 이 알고리즘은 정수형 2ⁿ 이내의 값을 bool array[n]과 결과로서 사용하는 방법이다. 예로 들어, {true, false, true}라는 논리형 배열이 있다고 할 때, 이를 101₂로 나타내면 (int)5라는 정수형 값만으로 긴 배열의 정보를 담을 수 있게 된다.

풀이 코드

#include <iostream>
#define MOD 1000000000
#define MAX_RANGE 1023

using namespace std;

// 1차원 배열 := 자리 길이
// 2차원 배열 := 맨 마지막 자리의 숫자
// 3차원 배열 := 9~0의 유무에 따른 비트마스킹(9~0 = 111...11)
int memo[101][10][1024];

int main() {
    // 찾고자 하는 자리의 수(문제에서의 N)
    int target_digit;
    cin >> target_digit;

    // 첫번째 자리 수에 1~9까지의 수들의 개수 1로 초기화
    // 첫 자리는 0이 될 수 없으므로, 0은 제외
    for(int curr_num = 1; curr_num <= 9; curr_num++)
        memo[1][curr_num][1 << curr_num] = 1;

    // 두번째부터 n자리까지 반복
    for(int index = 2; index <= target_digit; index++) {
        // 각 자리에 0~9이 들어가는 분기 생성
        for(int curr_num = 0; curr_num <= 9; curr_num++) {
            // 과거 숫자 이력에 대한 모든 분기 조사
            for(int bit_mask = 0; bit_mask <= MAX_RANGE; bit_mask++) {
                // 현재 자리의 숫자와 1만큼 차이나는 이전 분기를 현재 분기에 합산
                // bit_mask의 경우에는 해당 값이 유의미한 경우에만 값이 들어 있음
                int &curr_branch = memo[index][curr_num][bit_mask | (1 << curr_num)];
                if(curr_num > 0) {
                    curr_branch += memo[index - 1][curr_num - 1][bit_mask];
                    curr_branch %= MOD;
                }
                if(curr_num < 9) {
                    curr_branch += memo[index - 1][curr_num + 1][bit_mask];
                    curr_branch %= MOD;
                }
            }
        }
    }

    // 길이가 n이고, 0~9 범위 내 모든 숫자가 있었던 이력이 있는 수의 개수 정산
    int count = 0;
    for(int last_num = 0; last_num <= 9; last_num++)
        count = (count + memo[target_digit][last_num][MAX_RANGE]) % MOD;
    cout << count << endl;
    return 0;
}