[백준(BOJ)] #1562- 계단 수 (파이썬, PyPy3)

문제

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

1562번: 계단 수

 

---

문제 풀이

해당 문제는 쉬운 계단 수 문제의 심화 버전이라고 볼 수 있습니다. 계단 수를 구하는 것은 같지만, 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개인지를 구해야 합니다.

 

쉬운 계단 수를 풀때와 마찬가지로 동적 계획법을 사용했고, 추가로 비트마스크를 사용했습니다.

2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

[파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

2022.07.15 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 비트마스크(BitMask)

[파이썬으로 배우는 알고리즘] 비트마스크(BitMask)

 

사용할 수 있는 숫자 리스트를 비트에 매핑합니다.

 

924란 숫자로 예를 들어보겠습니다. 924라는 숫자에는 9, 2, 4가 쓰여 위와 같이 각 숫자가 있는 자리의 비트 값이 1이 된 것을 확인할 수 있습니다. 이를 십진수로 변환하면 532이고, 이런 비트 값을 dp테이블의 필드로 추가하여 경우의 수를 구할 수 있습니다.

 

dp[자리 수][마지막 숫자][사용된 숫자들의 비트 값]

마지막 숫자가 0보다 크면
dp[자리 수 + 1][마지막 숫자 - 1][사용된 숫자들의 비트 값 | 1 << 마지막 숫자 - 1] += dp[자리 수][마지막 숫자][사용된 숫자들의 비트 값]

마지막 숫자가 9보다 작으면
dp[자리 수 + 1][마지막 숫자 + 1][사용된 숫자들의 비트 값 | 1 << 마지막 숫자 + 1] += dp[자리 수][마지막 숫자][사용된 숫자들의 비트 값]

마지막 숫자가 0보다 큰 경우, 마지막 숫자에서 1을 뺀 숫자가 마지막 자리에 추가될 수 있습니다. 

이때 사용된 

(사용된 숫자들의 비트 값 | 1 << 마지막 숫자 - 1)

비트마스크 연산은 마지막 숫자에서 1을 뺀 값을 사용된 숫자들에 추가한다는 것을 의미합니다.

 

마지막 숫자가 9보다 작은 경우, 마지막 숫자에서 1을 더한 숫자가 마지막 자리에 추가될 수 있습니다.

이때 사용된 비트마스크 연산도 0보다 큰 경우와 마찬가지로 작용됩니다.

 

모든 숫자를 전부 사용할 경우 비트 값이 1111111111(2)이 되어야 하고, 이는 dp[입력받은 자리 수][0~9][1023]에 저장이 되어있을 겁니다.

 

---

구현

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    BIT_RANGE = 1 << 10
    NUM_RANGE = 10
    MOD = 1000000000
    N = int(input())

    # dp[자리 수][마지막 숫자][사용된 숫자들의 비트]
    # ex) 123 -> 0000001110
    dp = [[[0] * BIT_RANGE for _ in range(NUM_RANGE)] for _ in range(N+1)]

    # 0제외
    for i in range(1, NUM_RANGE):
        dp[1][i][1 << i] = 1

    # 자리 수
    for i in range(1, N):
        # 숫자 범위 j
        for j in range(NUM_RANGE):
            # 숫자 비트 표현
            for k in range(BIT_RANGE):
                # 맨 뒤에 있는 숫자가 0보다 크면 해당 숫자보다 1작은 숫자들이 올 수 있음
                if j > 0:
                    next = k | 1 << (j - 1)
                    dp[i+1][j-1][next] += dp[i][j][k]
                    dp[i+1][j-1][next] %= MOD
                # 맨 뒤에 있는 숫자가 9보다 작으면 해당 숫자보다 1큰 숫자들이 올 수 있음
                if j < 9:
                    next = k | 1 << (j + 1)
                    dp[i+1][j+1][next] += dp[i][j][k]
                    dp[i+1][j+1][next] %= MOD

    res = 0
    for i in range(NUM_RANGE):
        res += dp[N][i][BIT_RANGE-1]
        res %= MOD

    print(res)

결과