[KOI]두부 모판 자르기(bean curd)

[KOI]두부 모판 자르기(bean curd)

개인적으로 좋아하는 문제다.

2006년도 정보올림피아드 고등부 2번이다.

이걸 풀 땐 정말 정보에 대한 의지가 불타올랐던 시절이었는데..

암튼 시작한다.

<문제>

결국 두부모판을 어떻게 하면 가장 비싸게 팔수 있을지 쪼개라는 거다.

이런건 누가봐도 백트랙킹이다.

그런데 어떻게 백트랙킹을 해야하는가 - 이게 관건이다.

어려웠지만 그때 죽이되든 밥이되든 해서 풀었다.

지금 보면 참 대견하다.

일단 백트랙킹을 하되 일반적인 재귀적, 그런 백트랙킹은 안된다.

아 물론 될수 있겠지만 나로써 별로 상상이 안간다.

그리고 원래 재귀는 안할수록 좋다고 하지 않은가.

이건 재귀의 내부 스택을 이용하지 않은 그냥 스택 자체를 만들어서 풀어야된다고 결론지었다. 그리고 스택을 직접 만든 만큼 지금까지의 상태를 보존할 수 있는 다이나믹적 요소도 들어가야 한다.

시간복잡도는 2^(2N)*N 이 나온다.

다이나믹 점화식

D ij = i*i까지의 행렬만을 다루며 마지막 테두리의 모양이 j의 상태일 때의 최대치

막상 이 아이디어만 생각하면 별거 없다.

소스는 아래와 같다.

주석은 임의로 넣었고 디버깅용 코드가 약간 추가되있다.

#include<stdio.h> #include<memory.h> #define STACK_SIZE 5000 int N,bi,D[14][2500],V[5][5]={0,0,0,0,0,0,100,70,40,0,0,70,50,30,0,0,40,30,20,0,0,0,0,0,0}; int stack_w[STACK_SIZE],stack_h[STACK_SIZE],tail_w,tail_h; char dubu[14][14]; void input(){ FILE *fin=stdin; int i; fscanf(fin,"%d",&N); bi=(1<<N); for(i=1;i<=N;i++) fscanf(fin,"%s",dubu[i]+1); } inline int value(int x1,int y1,int x2,int y2){ int i,j; if(dubu[y1][x1]==0||dubu[y2][x2]==0) return 0; if(dubu[y1][x1]=='A') i=1; else if(dubu[y1][x1]=='B') i=2; else if(dubu[y1][x1]=='C') i=3; else i=4; if(dubu[y2][x2]=='A') j=1; else if(dubu[y2][x2]=='B') j=2; else if(dubu[y2][x2]=='C') j=3; else j=4; return V[i][j]; } int bin(int n){ int sum=0,cnt=1,tmp_n; tmp_n=n; while(!(tmp_n%2)&&tmp_n>0) cnt*=10,tmp_n/=2; while(n>0){ sum*=10; sum+=n%2; n/=2; } return sum*cnt; } void stack_w_push(int a,int b){ stack_w[tail_w++]=a; stack_w[tail_w++]=b; // printf("STACK_가로 PUSH동작 :: %d위치 %03d상태;\n",a,bin(b)); } void stack_h_push(int a,int b){ stack_h[tail_h++]=a; stack_h[tail_h++]=b; // printf("STACK_세로 PUSH동작 :: %d위치 %03d상태;\n",a,bin(b)); } int stack_w_pop(){ return stack_w[--tail_w]; } int stack_h_pop(){ return stack_h[--tail_h]; } void proc(){ int i,j,m,w_pos,w_state,h_pos,h_state,sum; for(i=1;i<=N;i++){ for(j=0;j<bi;j++){//i-1번째의 모양 // printf("현재 %d번째 라인, %03d모양\n",i,bin(j)); memset(stack_w,0,sizeof(int)*STACK_SIZE); stack_w_push(0,0);//pos,state while(tail_w>0){ w_state=stack_w_pop(); w_pos=stack_w_pop(); if(w_pos>N) break; // printf("STACK_가로 POP동작 :: %d위치 %03d상태;\n",w_pos,bin(w_state)); //현재 w_pos위치까지 모두 하였으므로 w_pos+1위치를 해야 한다. if(w_pos>=N){//가로 조합 종료. // printf("\n가로 조합:: %03d 상태로 완료. 세로 조합 루프 진입\n\n",bin(w_state)); memset(stack_h,0,sizeof(int)*STACK_SIZE); stack_h_push(0,0); while(tail_h>0){ h_state=stack_h_pop(); h_pos=stack_h_pop(); // printf("STACK_세로 POP동작 :: %d위치 %03d상태;\n",h_pos,bin(h_state)); if(h_pos>=N){// // printf("모두 조합 완료 :: 가로 상태 :: %03d\n",bin(w_state)); // printf("모두 조합 완료 :: 세로 상태 :: %03d\n",bin(h_state)); sum=0; for(m=0;m<N;m++){ if(w_state&(1<<m)){ sum+=value(m+1,i,m+2,i); m++; } if(h_state&(1<<m)){ sum+=value(m+1,i,m+1,i-1); } } // printf("sum::%d\n\n",sum); if(D[i][j]<D[i-1][(1<<N)-h_state-1]+sum) D[i][j]=D[i-1][(1<<N)-h_state-1]+sum; } if(h_pos<N){ stack_h_push(h_pos+1,h_state);//불변. if(i>1&&(j&(1<<h_pos))&&!(w_state&(1<<h_pos)))//가능시 조합. stack_h_push(h_pos+1,h_state+(1<<h_pos)); } } // printf("\n세로 조합 완료. 세로 조합 루프 탈출\n\n"); continue; } if(w_pos<N){ stack_w_push(w_pos+1,w_state);//변화 없음. if(w_pos<=N-2&&(j&(1<<w_pos)&&(j&(1<<(w_pos+1)))))//가능시 조합. stack_w_push(w_pos+2,w_state+(1<<w_pos)+(1<<(w_pos+1))); } } } } for(i=1;i<=N;i++){ for(j=0;j<bi;j++){ // printf("%d라인, %03d상태 : %d\n",i,bin(j),D[i][j]); } } } void output(){ FILE *fout=stdout; fprintf(fout,"%d",D[N][(1<<N)-1]); } int main(){ input(); proc(); output(); return 0; }