[백준 1562] 계단수 (C++)

1. 문제

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

1562번: 계단 수

 

2. 풀이

DP적 접근

비슷한 문제로 [백준 18044] 쉬운 쉬운 계단수가 있습니다. 이 문제를 먼저 이해해야 합니다. 이 문제는 기본적으로 [18044 쉬운 계단수]와 동일하게 최적 부분구조와 반복되는 부분문제를 가집니다. 하지만 쉬운 계단 수와는 다르게 "0부터 9까지 숫자가 모두 포함되어야 한다"는 조건이 추가되었습니다. 기존의 두 가지 정보를 이용한 DP 테이블로는 원하는 답을 얻을 수 없습니다. 따라서 부분문제를 해결할 때 "현재 구성된 계단수의 숫자의 조합"이라는 정보도 추가되어야 합니다.

 

비트마스킹

일단 최적 부분구조와 반복되는 부분문제를 확인합니다. 이를 바탕으로 정의한 부분문제는 다음과 같습니다. 이 때 다음 부분문제로 넘어가기 위해 전달해야 하는 필수 정보는 총 세 가지입니다. 바로 자리수, 마지막 숫자, 현재 구성된 계단수의 조합입니다. 여기 현재 구성된 계단수의 조합을 비트마스킹으로 저장해야 합니다.

예를 들어 3 4 5 4  의 계단수가 있을 때 0~9의 포함여부를 비트마스킹을 이용해 나타내면 0000111000₂가 됩니다. 이는 10진수 56으로 나타낼 수 있습니다. 이런식으로 2ⁿ의 모든 부분집합의 수를 한번에 나타낼 수 있습니다.

 

풀이

예를 들어 12번째 자리가 8로 끝날 때를 살펴보면, 다음 두 가지 경우에 8을 붙이면 됩니다.

11번째 자리수가 9로 끝나는 경우: ex) (1 2 3 4 5 6 7 8 7 8 9), (7 8 7 8 7 8 7 8 7 8 9), ...
11번째 자리수가 7로 끝나는 경우: ex) (1 2 3 4 5 6 7 8 9 8 7), (5 4 3 4 5 6 7 8 9 8 7), ...

11번째 자리가 9로 끝날 때도 살펴보면, 다음의 경우에 9를 붙이면 됩니다.

 10번째 자리가 8로 끝나는 경우: ex) (1 2 3 4 5 6 7 8 7 8), (1 2 3 4 5 6 7 8 9 8), ...

d[i][j][cmb]를 i번째 자리가 j로 끝나고 cmb의 조합을 가지는 경우의 수 라고 정의하면 점화식은 다음과 같습니다.

if i = 0, d[i][j][j | cmb] += d[i-1][j+1][cmb]
if i = 9, d[i][j][j | cmb] += d[i-1][j-1][cmb]
if 0 < i < 9, d[i][j][j | cmb] += d[i-1][j-1][cmb] + d[i-1][j+1][cmb]
단, d[1][k][1 << bit] = 1(첫번째 자리에 k가 오는 경우의 수는 항상 1)

여기서 중요한 점은 일반적인 dp와 달리  "= 연산자"가 아니라 "+= 연산자"를 사용해야 합니다. 현재 값이 업데이트될 때 0이라는 보장이 없기 때문입니다.

위의 두 번째 예시로 잠깐 검증을 해보면, d[11][9][100000000₂ | cmb]를 업데이트할 때 이미 d[10][8][0111111111₂]에 의해서 업데이트된 d[11][9][111111111₂]의 값이 존재합니다. 그런데 이후에d[10][8][111111111₂]에 의해서 다시 한번 업데이트되므로 현재 값에 더해서 저장해주어야 합니다.

 

3. 구현

#include<iostream>
#define MOD 1000000000
typedef long long LL;

using namespace std;
int N;
LL ans;
LL d[101][10][1<<10];

int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
  

    cin >> N;
    for (int i = 1; i < 10; i++) d[1][i][1 << i] = 1;

    for (int i = 2; i <= N; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int cmb = 0; cmb < (1 << 10); cmb++) {
                if (j == 0) d[i][j][cmb | (1 << j)] += d[i - 1][j + 1][cmb] % MOD;
                else if (j == 9) d[i][j][cmb | (1 << j)] += d[i - 1][j - 1][cmb] % MOD;
                else d[i][j][cmb | (1 << j)] += (d[i - 1][j - 1][cmb] + d[i - 1][j + 1][cmb]) % MOD;
            }
        }
    }
    for (int i = 0; i < 10; i++) ans = (ans + d[N][i][(1 << 10) - 1]) % MOD;
    cout << ans;

    return 0;
}

 

4. 정리

비트마스킹을 DP에 적용하는 방법을 알게 해준 소중한 문제입니다. 비트마스킹에 대한 완벽한 이해와 DP를 연습해볼 수 있는 퀄리티있는 문제입니다. 이 문제를 제대로 이해하고 풀면 간단한 다른 비트마스킹도 쉽게 다룰 수 있을것이라고 확신합니다.