[BOJ 10937] 두부 모판 자르기

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

10937번: 두부 모판 자르기

 

- 문제 요약

 

KOI 두부 공장에서 만들어내는 크기가 N × N (N ≤ 11)인 두부모판이 있다. 이 모판을 1×1 크기의 단위두부가 2개 붙어있는 형태의 포장단위(즉, 1×2 혹은 2×1 크기)로 잘라서 판매한다. 그런데 두부제조 공정상 모판에 있는 각 단위두부의 품질은 A, B, C, F급으로 분류되고, 잘린 포장단위의 두부 가격은 이 포장단위에 있는 두 개의 단위두부의 품질에 따라서 그림 1과 같이 정해진다.

그림 1. 포장단위의 가격표

두부모판의 크기와 단위두부의 등급이 주어질 때, 이를 포장단위로 잘라 받을 수 있는 총 가격의 최댓값을 구하는 프로그램을 작성하시오.

 

 

- 알고리즘 정리

 

비트마스크 DP로 풀 수 있는 문제입니다.

격자판 채우기 문제와 비슷한 방식으로 테이블을 관리하면서 문제를 해결해주면 됩니다.

 

 

- 코드 작성

#include<bits/stdc++.h>
using namespace std;

#define MAX 11
int n,dp[MAX*MAX][1<<12],cost[140][140];
string arr[MAX];

int f(int idx,int w){
	if(idx>=n*n-1){
		return 0;
	}
	int &ret=dp[idx][w];
	if(ret!=-1){
		return ret;
	}
	ret=f(idx+1,w>>1);
	if(w&1){
		return ret=max(ret,f(idx+1,w>>1));
	}
	int val=0;
	if((w&2)==0&&idx+1<n*n){
		val=cost[arr[idx/n][idx%n]][arr[idx/n][idx%n+1]];
		ret=max(ret,val+f(idx+2,w>>2));
	}
	if((w&(1<<n))==0&&idx+n<n*n){
		val=cost[arr[idx/n][idx%n]][arr[idx/n+1][idx%n]];
		int ww=w|(1<<n);
		ret=max(ret,val+f(idx+1,ww>>1));
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	memset(dp,-1,sizeof(dp));
	cost['A']['A']=100;
  	cost['A']['B']=cost['B']['A']=70;
  	cost['A']['C']=cost['C']['A']=40;
  	cost['B']['B']=50;
  	cost['B']['C']=cost['C']['B']=30;
  	cost['C']['C']=20;
  	cout<<f(0,0);
}

코드 제출 결과