[알고리즘 기법] 비트필드를 이용한 DP

스핑크스의 유명한 수수께끼 "목소리는 같지만 발이 4개가 되기도 하고 2개가 되기도 하고 3개가 되기도 하는 것은 무엇인가?"에 대한 다른 답안을 생각해볼 수 있는가? 이를 고안하기는 생각보다 힘들다. 필자는 10분의 구글링을 통해서 아무런 답을 찾지 못했으니까. 개인적으로는 아래 사진과 같이 카메라도 해답이 될 수 있다고 생각한다.

비트필드를 이용한 DP란?

위의 답이 무리라고 생각하는가? 무리가 맞다. 하지만 뭐 사람이라고 노년에 꼭 지팡이를 사용한다는 보장도 없으니 너그러히 넘어가자. 요점은 개발자라면, PS 능력을 키우려면 같은 것을 다르게 보고 응용할 능력이 있어야한다는 것이다.
우선 비트필드가 무엇인지 알아보자. 일단 이 글을 읽는 사람이라면 비트 연산을 모르는 사람은 없으리라 생각한다. 만약 있다면 기초적인 비트 연산과 관련하여 찾아보고 오기를 권장한다. PS에서 비트연산의 가장 기초적인 응용은 완전탐색에서의 응용이다. 예컨데 $N$개의 정수가 있고, 이의 부분집합의 합이 $S$가 될 수 있는지 묻는 문제가 있다고 하자. 많은 해결 방법이 있겠으나, $N$이 너무 크지 않다면 비트연산을 통한 완전탐색을 생각해볼 수 있다. $\lbrack1<<0, 1<<N)$

백준 예시

백준 1562번: 계단 수는 비트필드를 이용한 DP의 클래식한 문제라고 한다. 문제 스펙을 살펴보자.

해당 문제보다 쉬운 백준 10844번: 쉬운 계단 수는 2차원 캐시 $DP\lbrack N \rbrack\lbrack 10 \rbrack$가 있을 때 1에서 8까지 다음의 점화식으로 해결할 수 있다(1과 9는 별도로 처리해주면 된다).

$DP\lbrack i]\lbrack j] = (DP\lbrack i-1]\lbrack j+1] +DP\lbrack i-1]\lbrack j-1])\mod1000000000, (i, j \ge1)$

그렇다면 1562번 문제는 어떻게 해결하면 될까. 이 문제에서는 0에서 9까지의 모든 수가 포함되어 있는 경우만 결과값에 1을 추가해야한다. 그런즉 각 원소를 지나갈 때마다 위의 $j$값을 지나갔다는 표시를 해주어야하는데, 이를 배열로 기록하기는 너무 많은 시간과 공간이 소요된다. 그렇다면 이것을 비트필드로 저장하면 좋겠는데, 문제의 핵심은 이를 어떻게 풀어나갈 것인지에 달려있다.
필자는 가장 먼저 DP에 비트필드 값을 저장하는 쪽으로 생각을 했었다. 하지만 이렇게 하면 문제가 생긴다. 지금까지 발견한 계단 수를 $count$, 발견한 숫자(0-9)를 기록한 비트필드를 $digit$이라고 할 때, $\{count, digit\}$ 페어를 담고 있는 캐시 $DP\lbrack i]\lbrack j]$에서 특정 $i$, $j$값을 위의 점화식으로 계산산다고 가정해보자. 곰곰히 생각해보면 $DP\lbrack i-1]\lbrack j+1]$

FOR i 2...N
    FOR j 0...9
    	FOR k 0...(1<<10)-1
            j==0, j==9에 대한 예외 처리
            IF j!=9 AND j!=0
            	DP[i][j][k|1<<j] = (DP[i][j][k|1<<j]+DP[i-1][j-1][k]
            			+DP[i-1][j+1][k]) % 1000000000
            ENDIF
        ENDFOR
    ENDFOR
ENDFOR