[BOJ] 1562번 : 계단 수(DP, BitMask)

접근

비트마스크를 이용한 동적프로그래밍으로 해결하는 문제.

비트마스크.. 정말 하기싫었는데, 이게 동적 프로그래밍이랑 엮어서 나온다고? 최고의 조합이다.

그래도 모르면 안되는 개념이니, 비트마스크에 대한 기본적인 내용을 한번 정리해보고 가야겠다.

 

비트마스크(BitMask)

말그대로 비트를 마스크로 다루는 것이다. 

예를 들어 우리가 어떤 인덱스의 방문을 다루기 위해선 일반적으로 배열을 사용한다.

`visited = [False, False, True, False, True]` 이런식으로 방문여부를 저장하는 배열을 생성한 뒤 조작한다.

예시를 든 배열의 경우엔 2, 4번 인덱스가 방문을 했다는 것을 알 수 있다.

방문여부의 경우는 어떻게 보면 마스크 개념과 동일하다.

2, 4번 인덱스는 방문했으니까, 못 쓰겠구나! => `(some \ conditions) and not visited[i]` 

근데 이렇게 배열로 저장하는 것의 문제점은 용량을 많이 차지한다는 것이다.

그럼 Bit에 저장해서 사용해보면 어떨까?

비트마스크는 오른쪽부터 0의 인덱스로 생각하고 방문여부를 판단할 수 있다.

그럼 위와 같은 예시는 비트마스크로 이렇게 표현될 수 있을 것이다.

`[False, False, True, False, True] \rightarrow 10100_{(2)} = 20_{(10)}`

비트에 정보를 저장하지만 우리가 다루는 정보는 10진수이기 때문에 위와 같은 방문여부를 20이라는 숫자로 한번에 저장할 수 있는 것이다. 그렇지만 방문여부를 동적으로 다루기 위해선 비트의 조작에 대한 내용을 익혀야 한다.

비트 연산 자체는 간단하게 몇가지가 있다.

연산자	의미	예시
AND( & )	비교 비트가 모두 참(1)이면 참, 아니면 거짓(0)을 반환하는 연산.	101 & 011 = 001
OR( | )	비교 비트 중 하나라도 참(1)이면 참, 아니면 거짓(0)을 반환하는 연산.	100 | 010 = 110
XOR( ^ )	비교 비트가 다르면 참(1), 아니면 거짓(0)을 반환하는 연산.	101 ^ 011 = 110
NOT( ~ )	참(1)을 거짓(0)으로, 거짓(0)을 참(1)으로 반전시키는 연산	~ 011 = 100
LEFT SHIFT( << )	비트를 왼쪽으로 옮기는(SHIFT) 연산	101 << 2 = 10100
RIGHT SHIFT( >> )	비트를 오른쪽으로 옮기는 연산	101 >> 2 = 1

 

위와 같은 기본 연산들을 이용해서, 마스킹을 수행함으로 비트를 마스크형태로 사용할 수 있다는 것이다.

 

예를 들어 어떤 방문여부를 표시한 비트마스크가 아래와 같이 있다고 해보자.

`10100_{(2)}` 이 비트 마스크의 의미는 위에서 뭐라고 했는가? 2, 4번 인덱스가 방문해있다. 라고 해석할 수 있다고 말했다.

근데 여기서 3번 인덱스의 방문여부를 체크해주고싶다. 그러면 어떻게 할 수 있을까.

`1[0 -> 1]100_{(2)}` 이런 작업을 수행해줘야한다. 그럼 위의 연산들을 조합해서 생각해보자.

 

비트 추가

오른쪽에서 4번째 자리의 값을 1로 바꿔줘야한다.

=> 오른쪽에서 4번째 자리의 값을 1로 갖고있는 비트형태는? = `01000_{(2)}` = 1 << 3 LEFT SHIFT연산을 사용하면 비트 1을 우리가 원하는 비트의 자리로 보내줄 수 있겠구나!

=> 원래 비트마스크를 우리가 원하는 비트형태로 바꿔주는 방법은? = OR 연산을 사용하면, 원래의 비트들이 보장이 됨(1인 비트는 어차피 1이 나올거니까)

 

위와 같은 사고과정을 거쳐서 아래와 같은 수식에 도달할 수 있다.

$10100_{(2)} | (1 \ll 3) = 11100_{(2)} $

 

만약 그렇다면 3번 인덱스를 삭제할 수 있는 방법은 없을까?

 

비트 삭제

오른쪽에서 4번째 자리의 값만을 0으로 바꿔줘야한다.

=> 오른쪽 4번째 자리의 값만을 0을 갖는 비트형태 = `10111_{(2)}` = ~(1 << 3) 위의 과정과 동일하지만,  NOT 연산을 사용해서 바꿔줄 수 있구나!

=> 원래 비트마스크의 비트들은 보장하면서, 우리가 원하는 자리만 없애는 방법은? = 우리가 삭제하고자 하는 비트의 자리만 0이 되었으니까, AND연산을 사용하면 원래 비트들은 정보가 유지되면서, 우리가 원하는 비트만 0으로 만들어줄 수 있겠다.

 

위와 같은 사고과정을 거치면, 아래와 같이 도달할 수 있다.

$ 11100_{(2)} \& ~(1 \ll 3) = 10100_{(2)} $

 

이와 같이 기본 연산을 수행하는법을 익혔다면, 이제 문제를 해결해보자.

 

해결

계단 수는 인접한 자리의 수와의 차이가 1이 되는 수이다.

그러면서, 길이가 N이고, 0~9까지 숫자가 모두 등장하는 계단 수의 총 갯수를 구하라고 한다.

 

한번 생각해보자.

N자리까지의 계단수를 구하기 위해선, 하위 자릿수의 계단수를 구해나가는 과정이 필요할 것이다.

예를 들어,

한자릿수 계단 수는 1, 2, 3, 4, 5, 6, 7, 8, 9 등 이렇게 될 수 있고,

두자릿수 계단 수는 10, 12, 21, 23, 32, 34 ... 등이 될 수 있다.

결국 각 자릿 수 마다 들어올 숫자의 여부를 판단해서 갯수를 DP 배열에 저장해나가는 방식을 택할 수 있을 것이다.

근데 우리는 해당 자리까지 진행되면서 등장한 숫자들이 무엇이 있는지 판단할 순 없다.

예를 들어

[1 2 3], [3 2 3] 이 두 수 모두 계단 수이지만, 마지막 3이 나올 때 일반적인 DP로 해결한다면, 이전까지 전체의 계단 수는 알 수 있겠지만, 등장했던 숫자들은 알 수 있는 방법이 없다.

 

이 때 방문한 숫자들을 식별하기 위해서, 비트마스크를 활용한다.

먼저 DP 배열의 형태를 생각해보자.

위와 같은 일반적인 DP 형태라면, (자릿 수 N, 10[0 ~ 9 자릿 수 마지막의 숫자 경우])의 Shape을 생각할 수 있다. 

근데 우리는 비트마스크를 도입하여, 등장한 숫자들을 체크하기로 했으니 3차원으로 DP 배열을 구성할 수 있다.(자릿 수 N, 10[0 ~9], 1 << 10[등장할 수 있는 Bit의 조합 갯수])

 

마지막 차원의 1 << 10 의 의미는 등장할 숫자들이 0 ~ 9까지 10개이다. 그렇기 때문에 등장을 체크해주기 위해선 `0 000 000 000_{(2)}`의 자리만큼의 갯수가 필요한 것이다.

 

그럼 DP의 시작 선언은 어떻게 해야할까?

사고의 진행대로 하면, 당연히 첫째 자릿수 등장 숫자의 경우의 수 초기화가 필요할 것이다.

그럼 아래와 같이 진행해볼 수 있다.

dp = [[[0 for _ in range(1 << 10)] for _ in range(10)] for _ in range(N)] 

for k in range(1, 10):
    dp[0][k][1<<k] = 1

 

0번째 자릿수의 등장 가능 숫자는 1 ~ 9까지이다. 그러면서 각각의 등장 체크를 위해서 1 << k 번째의 배열을 1로 초기화 해준다.(첫째 자릿수의 등장 가능 갯수는 1개밖에 없으니까)

 

그럼 그 다음부터의 일반적인 점화식은 어떻게 될까?

일단 생각을 이어나가보자.

이제 둘째 자릿수부터 N번째 자릿수가지 DP배열을 채워나가야한다. 즉 N까지의 순회가 필요하다.

순회 내부에서 해당 자리의 등장 숫자들을 채워야한다.

그니까 첫번째에 1이 등장했으면, 그 다음 자리엔 0~9까지 모두 등장할 수 있으니까, 0~9까지의 순회가 필요할 것이다.

그리고 이번 자리에 등장한 숫자를 체크해줘야한다.

만약 이번 자리에 9가 등장했다고 하면, 이전에 등장했던 모든 경우(첫째자리가 8, 9인 계단 수)를 모두 더해줘야한다.

그럼과 동시에 해당하는 경우에 비트마스크 연산을 통해서, 9가 등장했다고 표시해주자.

한자릿 수라서 그렇지 이게 무슨말인지 잘 이해가 안갈 수 있다.

 

예를 들어

X X X X 7 와 같이 5자리인데, 앞서 등장한 계단 수들을 다 더해나가는건 엄청나게 복잡한 일이다 왜냐면 바로 앞은 6 또는 8밖에 없지만, 그 앞자릿수는? 그 앞의 앞자릿수는? 이렇게 나아가다보면 엄청나게 많은 경우가 생기기 때문이다.(X X 5 6 7, X X 7 6 7, X X 7 8 7 ... 등)

for i in range(1, N):
    for k in range(10):
        for bit in range(1<<10):
            if k - 1 >= 0:
                dp[i][k][bit | (1 << k)] += dp[i - 1][k - 1][bit] // 이전 계단 수에 등장한 모든 조합들을 더한다.
            if k + 1 <= 9:
                dp[i][k][bit | (1 << k)] += dp[i - 1][k + 1][bit]

 

그리고 보면 알겠지만, 비트마스크는 정말 효율적인 알고리즘처럼 보이지만 오히려 비효율적일 수 있다.

왜냐하면 체크하기위한 경우의 수가 `2^N` 단위이기때문에, 적당히 작은 하지만 배열로 하기엔 비효율적인 문제를 해결할 때 효율적으로 사용될 수 있을 것 같다.

 

사실 뭔가 다 아는거처럼 작성하고 있지만, 나도 정리하다보니 이해가 된거다. 내가 잘 참고했던 레퍼런스는 아래 블로그이다.

https://velog.io/@js43o/%EB%B0%B1%EC%A4%80-1562%EB%B2%88-%EA%B3%84%EB%8B%A8-%EC%88%98

[백준] 1562번: 계단 수

새롭게 배운 것을 익히고, 정리하는 과정을 거치니 어려워도 재미있고 더 이해가 잘 가는 것 같다.

코드

N = int(input())
dp = [[[0 for _ in range(1 << 10)] for _ in range(10)] for _ in range(N)] 
for k in range(1, 10):
    dp[0][k][1<<k] = 1
    
for i in range(1, N):
    for k in range(10):
        for bit in range(1<<10):
            if k - 1 >= 0:
                dp[i][k][bit | (1 << k)] += dp[i - 1][k - 1][bit]
            if k + 1 <= 9:
                dp[i][k][bit | (1 << k)] += dp[i - 1][k + 1][bit]
            dp[i][k][bit | (1 << k)] %= 1_000_000_000
            
cnt = 0
for k in range(10):
    cnt += dp[N-1][k][1023]
    cnt %= 1_000_000_000
    
print(cnt)