(1648) 격자판 채우기

https://www.acmicpc.net/problem/1648

단계별로 풀어보기

50단계(동적 계획법 4) 6번째

 

 

 

도미노의 한 가로줄에서 빈 공간을 0, 도미노가 있는 공간을 1로 두면 한 줄의 상태를 14비트의 수로 나타낼 수 있다.

DP[a][b]를 a-1번째 줄까지 도미노를 다 채우고 a번째 줄의 도미노 상태가 b인 경우의 수라고 하자. 이때 b의 범위는 0≤b<2^M이다. poss 배열을 b상태일때 가로 도미노로만 남은 빈칸을 채울 수 있는지 나타내는 불리언 변수 배열이라고 하자.

DP[a][b]에 대해, 이 b와 겹치지 않는 새로운 상태 b'을 세로 도미노로 채웠다고 생각하면 DP[a+1][b']이 되고, b와 b'으로 채우고 남은 공간을 가로 도미노로 채울 수 있는지 poss 배열로 검사해 가능하다면 DP[a][b]에서 DP[a+1][b']로 갈 수 있으므로 DP[a][b]의 값이 더해지게 된다. 이렇게 마지막 줄까지 반복해 poss[b]가 true인 모든 DP[N][b]를 더하면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define p 9901

int main() {
  int n, m, ans= 0;

  cin >> n >> m;

  if(n*m&1){
    cout << 0;
    return 0;
  }else if(n==1 || m==1){
    cout << 1;
    return 0;
  }
  
  vector dp(n, vector<int> (1<<m));
  vector<bool> poss(1<<m);
  
  for(int j=0;j<(1<<m);j++){  
    bool flag= true;
    
    for(int t=0;t<m;t++){
      if(j&(1<<t)){
        if(!flag){
          break;
        }
      }else{
        flag^= 1;
      }
    }

    if(flag){
      poss[j]= true;
      dp[1][j]= 1;
    }
  }
  
  for(int i=1;i<n-1;i++){
    for(int j=0;j<(1<<m);j++){
      if(!dp[i][j])  continue;

      for(int k=0;k<(1<<m);k++){
        if(j&k)  continue;

        if(poss[j|k]){
          dp[i+1][k]= (dp[i+1][k]+dp[i][j])%p;
        }
      }
    }
  }
  
  for(int j=0;j<(1<<m);j++){ 
    if(poss[j]){
      ans+= dp[n-1][j];
    }
  }
  
  cout << ans%p;
  
  return 0;
}

 

 

 

이런 형태의 DP를 푸는 고급 기법이 있는데, 정식 명칭은 브로큰 프로파일 DP라고 한다. 이 방법은 2차원 격자를 1차원처럼 한 줄로 늘어트린 뒤 현재 상태를 나타내는 now를 이용해 한 칸씩 이동하며 DP를 채우는 방식이다. now는 현재 칸 수, state는 현재 칸과 이후 M개 칸의 상태를 의미한다. 이때 비트 연산의 특성을 생각하면 state를 2^x로 나누는 것은 현재 상태가 x칸 앞으로 이동하는 것을 의미한다.

만약 now에서 state의 1의 비트가 차 있다면, 이미 이 칸은 도미노로 채워졌다는 의미이므로 바로 다음 칸으로 이동한다.

채워져 있지 않다면, 이 칸을 세로 도미노나 가로 도미노로 채울 수 있다. 세로 도미노로 채우면 now가 1 증가하고 state도 2로 나눈 뒤 (M+1칸 앞의 도미노도 같이 채워졌으므로) 맨 앞 비트에 1을 추가한 형태가 된다. 가로 도미노로 채우면 now가 2 증가하고 state는 4로 나눈 형태가 된다. 단 가로 도미노는 맨 오른쪽 열이 아니고 오른쪽 칸이 비어있을 때만 가능하다.

now가 n*m에 도달했을 때 state가 0이라면 0부터 n*m-1을 꽉 채웠다는 의미이므로 1을 추가한다. state가 0이 아니거나 n*m을 초과했다면 주어진 칸을 벗어나 도미노를 설치했다는 의미이므로 0을 추가한다.

 

이 방법도 처음에는 이해를 못 했었는데, Digit DP를 학습하는 과정에서 같이 이해하게 되었다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define p 9901

int main() {
  int n, m, ans= 0;

  cin >> n >> m;
  
  vector dp(n*m, vector<int> (1<<m, -1));

  auto func= [&](auto self, int now, int state) -> int {
    if(now==n*m && !state)  return 1;
    if(now>=n*m)  return 0;
    
    int& ret= dp[now][state];
    
    if(ret!=-1)  return ret;
    
    ret= 0;
    
    if(state&1){
      ret= self(self, now+1, state>>1);
    }else{
      ret= self(self, now+1, (state>>1)|(1<<(m-1)));
      if((now%m)!=(m-1) && !(state&2))  ret+= self(self, now+2, (state>>2));
    }
    
    return ret%= p;
  };
  
  cout << func(func, 0, 0);
  
  return 0;
}