백준 14700 - 넴모넴모 (Hard) [C++]

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

14700번: 넴모넴모 (Hard)

 

파이썬으로 시간 터져서 못했음

파란색 칸을 채우기 위해서는 \((M + 1)\) 개 칸의 상태 정보가 필요하다.

 

파란색 칸을 채우지 않는 경우: 

=> 항상 채우지 않는 선택을 할 수 있다.

 

채우는 경우:

- 가장 왼쪽 칸일 경우:

      => 항상 채울 수 있다.

- 가장 왼쪽 칸이 아닐 경우:

      => 왼쪽, 왼쪽 위, 위의 3개의 칸이 모두 색칠되지 않았다면 채울 수 있다.

 

#include <algorithm>
#include <iostream>
#include <cstring>
 
using namespace std;
#define endl '\n'
#define MOD 1000000007
 
int dp[301][1<<18];
int n, m;
 
int f(int idx, int bit){
    if (idx == n * m) return 1;
 
    if (dp[idx][bit] != -1) return dp[idx][bit];
 
    dp[idx][bit] = f(idx + 1, bit >> 1) % MOD;
 
    if (idx % m == 0){
        dp[idx][bit] += f(idx + 1, (bit >> 1) | (1 << m)) % MOD;
    }
    else{
        if (!(bit & (1 << m)) || !(bit & 2) || !(bit & 1)){
            dp[idx][bit] += f(idx + 1, (bit >> 1) | (1 << m)) % MOD;
        }
    }
 
    return dp[idx][bit] % MOD;
}
 
 
 
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m;
 
    if (n < m) swap(n, m);
 
    memset(dp, -1, sizeof(dp));
    cout << f(0, 0) << endl;
 
    return 0;
}