[BOJ] 1562번 : 계단 수

🔒 문제

45656이란 수를 보자.

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

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

0으로 시작하는 수는 계단수가 아니다.

⌨ 입력

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

🖨 출력

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

📚 예제

Ex)

10

1

📌 풀이

쉬운 계단 수의 심화 버전인것 같다. 어떻게 풀어야할 지 많은 고민을 했는데 비트마스킹을 사용하니까 쉽게 풀렸다.

dp[계단 수][일의 자리 수][0~9 중 어떤 수들 사용했는 지] 로 행렬을 만든다.

2차원 배열을 사용하던 쉬운 계단 수와는 달리 3차원 배열을 사용하여 문제를 풀 것이다.
행렬에는 경우의 수를 저장할 것이다.
1차와 2차까지는 쉬운 계단 수에서 사용하던 것과 같으니 문제가 없지만, 3차원이 문제다.

3차원의 인덱스 는 0~9까지의 수 중 사용한 수는 1 사용하지 않은 수는 0으로, 표시한 것이다.
비트를 사용하여 집합을 나타내는 것으로, 10bit로 사용한 수의 집합을 나타낸다.
즉 3차원의 인덱스 개수는 2의10승으로 1024개이고, 각 인덱스가 어떤 숫자를 사용했는지를 알려준다.

예를들어 45656 이란 수는 사용한 수들이 4,5,6으로 사용된 수를 10bit로 표현한다면 0001110000이고 이를 십진수로 변환하면 160이다.
그러면 이 수는 dp[4][6][160]에 카운팅이 되는 것이다.

또 다른 예시로 9876543210이란 수가 사용한 수를 10bit로 표현하면 111111111이고 이를 십진수로 변환하면 1023이다.
그러면 이 수는 dp[9][0][1023]에 카운팅이 되는 것이다.

즉 사용한 수라면 1로, 사용하지 않은 수는 0으로 표현하여 이 10bit 이진수를 십진수로 표현한 것이 3차원 인덱스가 되는 것이다.

무슨 소리인지 이해가 되었다면 다음 단계로 넘어가 보겠다.

행렬의 1차에는 계단 수, 2차에는 일의 자리 수, 3차에는 사용한 수들을 비트로 표현한 수가 들어간다고 했다.
그러면 식으로 나타내서 이해해보자.

dp[n][m][k]라 하자.

1. n == 0
   0을 제외한 m이 1~9까지의 숫자들은 모두 1개씩의 계단 수를 가질 것이다. 이 수들의 k를 결정하는 법을 보겠다.

1) m == 0 => k == 0
0일때는 카운트하면 안되니까 k == 0 에 0을 대입한다
dp[0][0][0] = 0

2) m == 1 => k == 2
m이 1이란 소리는 숫자 1을 사용한 것이므로 사용한 수를 비트로 나타내면 0000000010이고 따라서 k는 2이다.
dp[0][1][2] = 1

3) m == 2 => k == 4
m이 1이란 소리는 숫자 2를 사용한 것이므로 사용한 수를 비트로 나타내면 0000000100이고 따라서 k는 4이다.
dp[0][2][4] = 1

4) m == 3 => k == 8
m이 1이란 소리는 숫자 3을 사용한 것이므로 사용한 수를 비트로 나타내면 0000001000이고 따라서 k는 8이다.
dp[0][3][8] = 1

5) m == 4 => k == 16
m이 1이란 소리는 숫자 4을 사용한 것이므로 사용한 수를 비트로 나타내면 0000010000이고 따라서 k는 16이다.
dp[0][4][16] = 1

6) m == 5 => k == 32
m이 1이란 소리는 숫자 5을 사용한 것이므로 사용한 수를 비트로 나타내면 0000100000이고 따라서 k는 32이다.
dp[0][5][32] = 1

7) m == 6 => k == 64
m이 1이란 소리는 숫자 6을 사용한 것이므로 사용한 수를 비트로 나타내면 0001000000이고 따라서 k는 2이다.
dp[0][6][64] = 1

8) m == 7 => k == 128
m이 7이란 소리는 숫자 7을 사용한 것이므로 사용한 수를 비트로 나타내면 001000000이고 따라서 k는 128이다.
dp[0][7][128] = 1

9) m == 8 => k == 256
m이 8이란 소리는 숫자 8을 사용한 것이므로 사용한 수를 비트로 나타내면 0100000000이고 따라서 k는 256이다.
dp[0][8][256] = 1

10) m == 9 => k == 512
m이 9이란 소리는 숫자 9을 사용한 것이므로 사용한 수를 비트로 나타내면 100000000이고 따라서 k는 512이다.
dp[0][9][512] = 1

2. n >= 1
   여기서부터 비트마스킹이 제대로 사용된다.
   1) m == 0
   m이 0이라는 소리는 끝 자리에 0을 넣는다는 소리이고, 다시 말하면 사용한 숫자에 0이 추가된다는 것이다.
   0이 이미 사용됐었다면 0의 bit를 그대로 1로 유지해야하고, 0이 처음 사용된다면 0의 bit를 0에서 1로 바꿔줘야한다.
   이것을 가능하게 하는 방법은 비트마스킹의 or 연산이다.
   따라서 dp[n-1][m+1][k] 0~1023까지의 모든 k를 확인하면서 dp[n][m][k]의 k|(2^0)의 위치에 지금까지 조건을 만족한 수들의 개수를 넣는다.

2^0과 3차원 인덱스를 or연산 하는 이유는 10bit의 각 bit가 숫자들의 유무를 나타내고 0은

이해하기 편하게 식으로 나타내면 이런 느낌이다.

for i in range(1024):
    k = i|(2 ** m)
    dp[n][m][k] += dp[n-1][m+1][i] 

2) m == 9
m이 9라는 소리는 끝 자리에 9를 넣는다는 소리고, 사용한 수에 9도 포함이 된다는 소리다.
위의 방법 처럼 9의 bit가 0이면 1로, 1이면 1을 유지시키기 위해 or연산을 사용할 것이고 식으로 바로 확인해 보겠다.

for i in range(1024):
    k = i|(2 ** m)
    dp[n][m][k] += dp[n-1][m-1][i] 

3) 나머지 m

for i in range(1024):
    k = i|(2 ** m)
    dp[n][m][k] += dp[n-1][m-1][i]
    dp[n][m][k] += dp[n-1][m+1][i]

길이가 N이면서 0~9까지의 숫자가 모두 등장하는 계단 수는 인덱스k가 1023인 곳에 저장된 수와 같다

즉 n이 N-1이고, m은 0~9 이면서 k값이 1023인 곳에 저장된 수들을 모두 더하면 그것이 정답이다.

for m in range(10):
    ans += dp[N-1][m][1023]

🔑 python 코드

import sys
N = int(sys.stdin.readline())
dp = [[[0 for _ in range(2**10)] for _ in range(10) ] for _ in range(N)]
dp[0][0][0] = 0

for i in range(1,10):
    dp[0][i][2**i]+=1

for i in range(1,N):
    for j in range(10):
        if(i == 1 and j == 1):
            for k in range(2**10):
                if(dp[i-1][j+1][k]!=0):
                    a = k|2**j
                    dp[i][j][a] += dp[i-1][j+1][k]

        elif(j == 0):
            for k in range(2**10):
                if(dp[i-1][j+1][k]!=0):
                    a = k|2**j
                    dp[i][j][a] += dp[i-1][j+1][k]

        elif(j == 9):
            for k in range(2**10):
                if(dp[i-1][j-1][k]!=0):
                    a = k|2**j
                    dp[i][j][a] += dp[i-1][j-1][k]

        else:
            for k in range(2**10):
                if(dp[i-1][j-1][k]!=0):
                    a = k|2**j
                    dp[i][j][a] += dp[i-1][j-1][k]

                if(dp[i-1][j+1][k]!=0):
                    a = k|2**j
                    dp[i][j][a] += dp[i-1][j+1][k]

ans = 0

for i in range(10):
    ans+=dp[N-1][i][1023]

print(ans%1000000000)

머리로는 다 이해했는데 설명을 하려니 용어를 어떻게 써야할지 어떻게 설명하고 배치는 어떻게 할지 등 너무 어렵다.
내가 아는 지식을 남에게 전달하는 방법을 블로그를 쓰면서 터득할 수 있길 바란다,,