정올 고급 강의 9차시 정리

[두부모판 자르기](backtracking 기법)

KOI 두부 공장에서 만들어내는 크기가 n*n(n은 11이하의 자연수)인 두부 모판이 있다.

이 모판을 1*1크기의 단위두부가 2개 붙어있는 형태의 포장단위 (즉, 1*2 혹은 2*1크기)로 잘라서 판매한다.

그런데 두부제조 공정상 모판에 있는 각 단위두부의 품질은 A, B, C, F급으로 분류되고, 잘려진

포장단위의 두부 가격은 이 포장단위에 있는 두 개의 단위두부의 품질에 따라서 다음과 같이 정해진다.

	A	B	C	F
A	100	70	40	0
B	70	50	30	0
C	40	30	20	0
F	0	0	0	0

포장 단위에 있는 두 단위두부가 [A, A]급이면 100원을 받고, [A, B]급이면 70원을 받는 식이다.

F급이 하나라도 있으면 한 푼도 받을 수 없다.

두부 모판의 품질이 주어질 때, 가장 높은 가격을 받도록 두부 모판을 1*2 혹은 2*1 크기의 포장단위들도 자르고자 한다.

두부 모판의 크기는 n(2<=n<=11)

현재 a행 b열에 대해서

1. (a, b)+(a+1, b)로 판매(세로)

2. (a, b)+(a, b+1)로 판매(가로)

3. 판매하지 않음

#include <stdio.h>
 
int chk[20][20], p[26][26]={{100,70,40},{70,50,30},{40,30,20}}/*두부의 가격*/,n;
char A[20][20];
 
int f(int a, int  b){ //a행 b열
    int ans = 0;
    if(a==n) return 0;
    if(b==n) return f(a+1, 0);
    if(chk[a][b]==0){ //탐색을 아직 하지 않았음
        chk[a][b]=1; //이제 탐색함
        if(b+1<n&&chk[a][b+1]==0){ //b+1이 가로줄의 마지막이 아니고 && b+1이 채크 안되어 있으면 탐색
            chk[a][b+1]=1;
            ans=max(ans,f(a,b+2)+p[A[a][b]-'A'][A[a][b+1]-'A']); //b+b+1이 현재까지 구한값보다 많으면 갱신
            chk[a][b+1]=0; //재귀함수가 끝났으므로 체크 해제-백트래킹
            }
        }
        if(a+1<n&&chk[a+1][b]==0){ //b+1이 가로줄의 마지막이 아니고 && b+1이 채크 안되어 있으면 탐색
            chk[a+1][b]=1;
            ans=max(ans,f(a,a+1)+p[A[a][b]-'A'][A[a+1][b]-'A']); //b+b+1이 현재까지 구한값보다 많으면 갱신
            chk[a+1][b]=0; //재귀함수가 끝났으므로 체크 해제-백트래킹
            }
        }
        ans=max(ans,f(a,b+1)); //여기 있는 두부를 사용하지 않겠다
        chk[a][b] = 0; //백트래킹
        else{
            ans=max(ans, f(a, b+1)); //두부를 전혀 사용하지 않겠다??
        }
        return ans;
    }
}

↑

(11*11)^3 걸림 = 3^121 시간 너무 오래걸림

시간을 줄임

f(a, b, bit-state) = "현재 a행 b열을 탐색하는 상태에서 bit-state의 값으로 다음 개의 칸이 채워져 있을 때까지의 최대 판매 이득"

DT[a][b][bitstate]

시간복잡도 O(2^n*n^2)

#include <stdio.h>
#define cu(1<<n) //1000
#define rt (1<<(n-1))
#define dn(1)
#define M (1<<(n+1))
 
int p[4][4]={100,70,40,0,70,50,30,0,40,30,20,0,0,0,0,0};
int n, tb[12][12], m[12][12][1<<13];
 
int max(int a, int b) { return a>b ? a:b;}
 
int f(int x, int y, int s){
    int ans = 0;
    if(a==n) return 0;
    if(b==n) return f(a+1, 0);
    if(!m[x][y][s]){
        if(!(s&cu)){
            if(y+1<n&&!(s&rt)){ //경계조건 && 놓을 수 있는지 비트엔드 연산으로 확인
                m[x][y][s] = max(m[x][y][s], f(x,y+2,(s<<2)%M+p[tb[x][y]][tb[x][y+1]]);
            }
            if(x+1<n&&!(s&dn)){ 
                m[x][y][s] = max(m[x][y][s], f(x,y+1,((s|dn)<<1)%M+p[tb[x][y]][tb[x+1][y]]);
            }
        m[x][y][s]=max(m[x][y][s], f(x, y+1, (s<<1)%M));
        }
        else m[x][y][s]=max(m[x][y][s], f(x, y+1, (s<<1)%M));
    }
    return m[x][y][s];
}
 
int main(){
    char t;
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf(" %1c", &t);
            tb[i][j]=(t=='F' ? 3:t-'A');
        }
    printf("%d\n", f(0,0,0));
    return 0;
}