백준 1562 - 계단 수

 

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

1562번: 계단 수

 

이 문제보다 조건이 단순한 '쉬운 계단수' 문제에서 적용했던 dp 풀이법을 발전시켜서 풀 수 있다.

0부터 9까지 정수의 등장 여부를 확인하기 위해 비트마스킹 기법을 활용한다.

 

dp식 정의

dp[i][j][k] := 비트필드 j의 숫자들로 이뤄진, 맨 앞자리가 k로 시작하는 i자리 계단수의 갯수

비트필드는 10자리로, 0~9까지 정수의 등장 정보를 저장한다.

 

예를 들어 dp[2][0000000110(2)][1]은 1과 2를 사용하며 맨 앞자리가 1인 2자리 계단수이므로 가능한 계단수는 12 하나 뿐이다.

 

문제에서 요구하는 값은 N자리, 모든 정수를 사용하는 비트필드 (1111111111), 맨 앞자리가 0이 아닌 계단수의 개수의 총합이므로, dp[N][1111111111(2)][1] 부터 dp[N][1111111111(2)][9]까지의 합을 계산해 얻을 수 있다.

 

초깃값

한 자리 자연수는 모두 계단수에 포함된다. 각 자연수 i의 비트필드는 1 << i로 나타낼 수 있으므로, 코드 상에서 dp배열을 다음과 같이 초기화할 수 있다.

//한 자리, 비트필드는 (i + 1)번째 자리만 1, 맨 앞자리 수는 i
for (int i = 0; i <= 9; i++)
    dp[1][1 << i][i] = 1;

점화식

스탠다드한 문제 '외판원 순회'와 비슷하게 진행된다. 자릿수를 1씩 증가시켜가며 매 자릿수마다 0000000001부터 1111111111까지 1000개 가량의 비트필드를 모두 확인한다.

for (int i = 1; i < N; i++) {

    for (int j = 1; j < (1 << 10); j++) {

이제 0부터 9까지의 정수 k에 대해, k가 필드 j에 포함되고 필드 j와 맨 앞자리 k를 가지고 계단수를 만들 수 있는 지 검사한다. 포함 여부는 비트 연산자를 통해, 계단수 확인은 현재 dp[i][j][k]에 저장된 값을 통해 검사할 수 있다.

 

예를 들어 j = 0011100101, k = 5일 경우 k는 필드 j에 포함된다. 그러나 필드의 숫자 0, 2, 5, 6, 7을 모두 사용해 계단수를 만드는 건 불가능하므로 dp[i][j][k]에는 유효한 갯수가 저장되어있지 않다. ex) -1

if ((j & (1 << k)) == 0) continue;
if (dp[i][j][k] < 0) continue;

 

만약 현재 필드 j와 앞 자리 수 k에 대해 계단수가 존재한다면, 이 계단 수의 앞에 k + 1, k - 1 중 0 ~ 9 범위 내의 정수를 추가해 새로운 계단수를 만들 수 있다.

 

간단한 예를 들어보자.

4로 시작하는 3자리 계단수는 432, 434, 454, 456 4개가 있으며, 각각을 dp식 정의를 이용해 나타내면 다음과 같다.

계단수	dp식 정의
432	dp[3][0000011100][4]     (2,3,4)
434	dp[3][0000011000][4]     (3,4)
454	dp[3][0000110000][4]     (4,5)
456	dp[3][0001110000][4]      (4,5,6)

이제 이 4개의 계단수 앞에 3, 5를 붙여 총 8개의 계단수를 만들 수 있다. 8개는 좀 많으니 일부만 확인해보자.

계단수	dp식 정의	확장	dp식 정의
432	dp[3][0000011100][4]     (2,3,4)	3432	dp[4][0000011100][3]     (2,3,4)
		5432	dp[4][0000111100][5]     (2,3,4,5)
456	dp[3][0001110000][4]      (4,5,6)	3456	dp[4][0001111000][3]     (3,4,5,6)
		5456	dp[4][0001110000][5]     (4,5,6)

 

다시 말해, 현재 dp[i][j][k]에 속하는 모든 계단수에 대해 k + 1과 k - 1 중 유효한 정수를 앞에 추가하면 이 계단수들을 dp[i+1][k + 1을 추가한 필드][k+1], dp[i+1][k - 1을 추가한 필드][k - 1]에 속하는 계단수로 만들 수 있다. 코드로 나타내면 다음과 같다.

if (k + 1 <= 9) {
    ll& up = dp[i + 1][j | (1 << (k + 1))][k + 1];
    
    //dp[i][j][k]를 통해 생성한 새로운 계단수를 추가
    up = up < 0 ? dp[i][j][k] : up + dp[i][j][k];
    
    //오버플로우 방지
    up %= div;
}

if (k - 1 >= 0) {
    ll& down = dp[i + 1][j | (1 << (k - 1))][k - 1];
    down = down < 0 ? dp[i][j][k] : down + dp[i][j][k];
    down %= div;
}

 

풀다보면 0을 관리하기가 까다로웠을 것이다. 참고로 말하면 0과 9는 1 차이 난다고 취급하지 않아 90은 계단수가 아니다. 어쨌든 0을 관리하기 위해서는, 그냥 0으로 시작하는 계단수도 계산 과정에 포함하면 된다. 마지막 카운트에서만 무시하라.

 

전체 코드

//dp식 정의
ll dp[101][1 << 10][10];

int main() {
    FASTIO;

    int N;
    cin >> N;
    ll div = 1000000000;
	
    //전체 초기화
    memset(dp, -1, sizeof(dp));
	
    //초깃값 설정
    for (int i = 0; i <= 9; i++)
        dp[1][1 << i][i] = 1;

	//자릿수, 필드, 맨 앞자리 3중 반복문
    for (int i = 1; i < N; i++) {

        for (int j = 1; j < (1 << 10); j++) {
			
            //0도 같은 방식으로 처리
            for (int k = 0; k <= 9; k++) {
				
                //포함 여부, 계단수 존재 여부 확인
                if ((j & (1 << k)) == 0) continue;
                if (dp[i][j][k] < 0) continue;
				
                //유효한 계단수가 있으면 맨 앞에 정수를 추가해
                //동일 개수의 새로운 계단수를 생성
                if (k + 1 <= 9) {
                    ll& up = dp[i + 1][j | (1 << (k + 1))][k + 1];
                    up = up < 0 ? dp[i][j][k] : up + dp[i][j][k];
                    up %= div;
                }

                if (k - 1 >= 0) {
                    ll& down = dp[i + 1][j | (1 << (k - 1))][k - 1];
                    down = down < 0 ? dp[i][j][k] : down + dp[i][j][k];
                    down %= div;
                }
            }
        }
    }

    ll res = 0;
	
    //마지막 계산에서는 0을 제외
    for (int i = 1; i <= 9; i++) {
        if (dp[N][(1 << 10) - 1][i] > 0)
            res = (res + dp[N][(1 << 10) - 1][i]) % div;
    }

    cout << res << endl;
}