[백준]컨닝(1014)

문제 링크 : [백준]컨닝(1014)

1014번: 컨닝

 

문제 설명

N * M 의 격자가 주어지고, 각 칸에는 학생이 앉을 수 있는 경우(.)와 앉을 수 없는 경우(x)가 주어집니다.

이때, 모든 학생이 자신과 인접한 왼쪽, 오른쪽, 오른쪽 위 대각선, 왼쪽 위 대각선에 자리를 비우도록 하여 최대한 많은 사람을 앉게 하는 경우, 몇 명까지 앉힐 수 있는지 구하세요.

입력

T(테스트 케이스의 수)

N(격자의 세로 크기, 1 <= N <= 10)

M(격자의 가로 크기, 1 <= M <= 10)

격자 정보

4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....

 

출력

4
1
2
46

 

카테고리

#DP #비트마스크

 

시간 복잡도 상한

매우 커도 될 것 같아요??(O((M*M)!)만 아니면 될 듯??)

 

해결 방법

1. 당연히 모든 경우를 다 돌려보면 답은 구할 수 있으나, 2¹⁰⁰이라서 타임아웃이 나올거예요.
2. 그러면 중복이 없는지를 살펴봅시다.
3. 윗줄의 케이스가 완성이 된다면, 그에 따른 아랫줄의 최댓값은 변하지 않을거예요.
4. 따라서 몇번째 줄인지와 윗줄의 상태값을 메모이제이션하여 시간복잡도를 줄일 수 있습니다.
5. 그러면 윗줄의 상태는 어떻게 저장을 할지 고민해봅니다.
6. 각각의 칸은 앉거나 앉지 않거나 두가지 상태로 구분이 되고, 이런 경우 비트마스크를 사용하여 각 칸의 상태를 1bit만 사용하여 저장할 수 있습니다.
7. 그러면 DP 배열의 칸수는 줄 수 10, 상태 1<<10=1,024 즉 10,240칸이 됩니다.
8. 각 칸을 채우는데, 최대 1,024가지 경우를 살펴보아야 하니, 대략 10,000,000번의 연산 안에 끝날 수 있습니다.(실제로는 비트 사용 여부에 따라 훨씬 줄어 들 것 같습니다.)
9. 한 줄에 대한 모든 상태를 만들어 보고, 그 상태를 다음줄을 확인 할 때 넘겨줍니다.
10. 다음 줄에 대한 확인을 하면서, 앉을 수 있는 자리라면, 자신의 왼쪽, 왼쪽 위, 오른쪽 위를 살펴보아 앉을 수 있는지 여부를 확인합니다.
    1. 오른쪽은 확인 안합니다.(사실 왼쪽부터 살펴보니 확인할 필요도 없거니와, 왼쪽에서 오른쪽을 검사하나 오른쪽에서 왼쪽을 검사하나 동일한 로직이기 때문에 하나만 처리하면 됩니다.)
11. 기저 조건을 만나면, 마지막 줄에서 몇 자리에 사람을 앉혔는지 반환합니다.
    1. 켜진 비트 수를 세면 됩니다.
12. 끝까지 올라가면서 모든 경우에 몇명이 앉았는지 확인합니다.

시간복잡도

대략 천만??

코드

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int t,n,m,i,d[10][1<<10];
bool e[10][1<<10];
char s[10][11];
int r(int p,int t);
int u(int p,int t,int z,int x){
    int a=0;
    if(x==m){
        int k=0,q=z;
        while(q){
            k+=(q&1);
            q>>=1;
        }
        return r(p+1,z)+k;
    }
    bool lu=p&&x&&s[p-1][x-1]=='.'&&(t&(1<<(x-1)));
    bool ru=p&&x<m-1&&s[p-1][x+1]=='.'&&(t&(1<<(x+1)));
    bool ll=x&&s[p][x-1]=='.'&&(z&(1<<(x-1)));
    if(s[p][x]=='.'&&!lu&&!ru&&!ll)a=u(p,t,z|(1<<x),x+1);
    return max(a,u(p,t,z,x+1));
}
int r(int p,int t){
    int&a=d[p][t];
    if(p==n)return 0;
    if(e[p][t])return a;
    e[p][t]=1;
    return a=u(p,t,0,0);
}
int main(){
    scanf("%d",&t);
    while(t--){
        memset(d,0,sizeof(d));
        memset(e,0,sizeof(e));
        scanf("%d%d",&n,&m);
        for(i=0;i<n;i++)scanf("%s",s[i]);
        printf("%d\n",r(0,0));
    }
}