BOJ 18292 - NM과 K (2)

문제 태그 : https://www.acmicpc.net/problem/18292

문제 소개

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다.

문제 풀이

숫자가 작고 인접한 칸을 고르지 않는다는 조건. Bit를 활용한 DP가 풀이로 바로 떠오른다. 
한 줄에 대해서 0~2^m 까지를 고르는 경우를 모두 고려 해주면 된다. 각 숫자별로 켜져 있는 비트가 골라진 칸 이라고 생각하면 된다.
dp[i][j][k]= i 번째 줄까지 j 개의 칸을 선택했으며, 마지막 (i번째) 줄 의 선택된 모양이 k일때 최댓값이다.

총 테이블의 크기는 O(NK 2^M)이고, 전 줄의 2^M의 경우에 대해서 모두 따져봐야 하므로 총 시간복잡도는 O(NK 4^M)이 된다.

구현 & 코드

if(i&j)는 i와 j가 동시에 켜진 코드가 있는지를 확인한다. i에 위의 상황, j에 아래의 상황을 넣으면 위아래로 연속된 두 칸을 선택했는지를 확인할 수 있다.
사용한 칸 수를 알기 위해서는 __builtin_popcount(x)를 잘 활용해 주면된다. x의 켜져있는 비트의 갯수를 세주는 내장함수 이다.

전처리로는 1. 각 줄 별로 고른 칸에 따른 얻는 점수의 값, 2. k의 형태로 고를 수 있는지 (가로로 연속된 두 칸을 고르지 않았는지) 정도를 해주면, dp 과정에서 훨씬 더 매끄럽게 식이 구현되어진다.

Bit를 활용한 DP에 쓰이는 테크닉을 많이 볼 수 있었던 정석적인 문제이다.

#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);
 
}