Techniques In DP (1) - bitmask

DP에서 쓰이는 테크닉들 중 처음으로 비트마스크(Bitmask)에 대해서 설명하려고 한다.
보통 DP 말고 다양한 곳에서 쓰이기도 하지만 이글에서는 DP에 쓰이는 방향으로 초점을 두고 진행할 예정이다.

Bitmask란?

Bitmasking 기법이라고도 불리며, Bit에다가 masking을 하는 것이다. 다시 말해 DP값의 중요한 요소중 한가지인 '상태'를 배열등이 아닌 한 개의 숫자로 표현하겠다는 것이다. 예를 들어 bool arr[4] 배열이 채워질 수 있는 모든 경우의 수를 0~15의 수에 대응을 시켜 표현 하겠다는 것이다.

언제 & 왜?

Bit masking은 보통 제한이 굉장히 작으면서, 모든 경우를 다 표현하고 싶을 때 사용한다. 이때 비트를 사용하기 때문에 스케일은 당연히 지수 스케일이며, 어떠한 한 종류에 대해 둘 중 하나인 상황만 표현할 수 있다.
예를 들면 16개의 전구중 임의의 전구에 불이 들어와 있는 상태를 표현한다던지, 어떠한 20개의 노드중 내가 지금까지 지나온 노드들을 표현한다던지 하는 방식이다. 

그렇다면 왜 굳이 숫자에 담아서 상태를 표현하는 것일까?
답은 '편하니까'이다. bool arr[16]의 모든 배열의 상태를 표현하기는 정말 복잡하고 코드도 굉장히 길어진다. 하지만 비트마스킹 기법을 이용하면 0~65535의 숫자로 표현이 가능해진다. 반복문을 사용하기에 최적의 조건이다.
또한 비트마스팅에서 아쉬울 수도 있는 부분들을 보완해주는 장치들도 굉장히 많다.

예를 들면 아래의 코드는 x에서 켜진 비트의 수를 반환해 준다.

__builtin_popcount(x)

아래의 코드는 x에서 i번째 비트가 켜졌는지를 확인할 수 있다.

if(x&(1<<i))

이런식으로 간단히 비트에 접근할 수 있는 방법이 많아 배열에서의 arr[i] 같은것을 거의 완벽히 대체 할 수 있다.

문제에서의 적용

문제는 BOJ 18292 NM과K (2) 를 들고 왔다.

문제에서 찾을 수 있는 상태는 3가지이다. 어떤 줄까지 선택했으며, 총 몇칸을 선택했고 마지막 줄은 어떠한 칸들을 선택했다.
따라서 dp[i][j][k]=i번째 줄까지 j개의 칸을 선택했고 k의 형태로 마지막 줄을 선택했을때 최댓값이 될것이다.

여기서 k는 어떻게, 즉 선택된 한 줄의 칸의 상태를 담아낸다. 따라서 이를 비트마스킹을 이용해 해결해주면 된다.

인접한 두 칸을 선택하지 않는다는 조건은 k의 값에서 연속된 두 비트가 켜져있지 않음을 확인하고, i-1 번째 줄의 k값과 현재 확인하는 k값을 &을 취해서 0인지 확인하면 된다.

켜진 비트 수나 가능한 k같은 경우는 전처리를 해주는 방향으로 진행했다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll dp[15][55][3020];
ll arr[15][15];
ll pre[15][3020];
ll chk[3020];
ll bc[3020];
int main(){
    ll i,j,k,l,m,n,mm,c,bk;
    scanf("%lld %lld %lld",&n,&m,&c);
 
    for(i=1;i<=n;i++)
        for(j=0;j<m;j++)
            scanf("%lld",&arr[i][j]);
 
    mm=(1<<m)-1;
    for(i=1;i<=n;i++)
        for(j=0;j<=mm;j++){
            bc[j]=__builtin_popcount(j);
            for(k=0;k<m;k++)
                if(j&(1<<k))
                    pre[i][j]+=arr[i][k];
        }
 
    for(i=0;i<=14;i++)
        for(j=0;j<=53;j++)
            for(k=0;k<=3000;k++){
                dp[i][j][k]=-1e18;
                if(i==0&&j==0) dp[i][j][k]=0;
            }
 
    for(i=0;i<=mm;i++)
        for(j=1;j<m;j++)
            if((i&(1<<j))&&(i&(1<<(j-1)))) chk[i]=1;
        
    
 
    for(i=1;i<=n;i++)
        for(k=0;k<=mm;k++){
            if(chk[k]) continue;
            for(bk=0;bk<=mm;bk++)
                for(j=bc[k];j<=c;j++)
                    if((k&bk)==0) dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-bc[k]][bk]+pre[i][k]);
        }
    
    ll ans=-1e18;
    for(i=0;i<=mm;i++)
        ans=max(ans,dp[n][c][i]);
    printf("%lld",ans);
 
}

추천 문제

BOJ 2098 외판원 순회
BOJ 1014 컨닝