[문제해결을 위한 창의적 알고리즘] 두부 자르기 (고급, p207)
이 문제는 한국정보올림피아드에 출제되었던 문제인데, 굉장히 어렵다고 알려져 있다. 실제로 어떻게 동적계획법을 세워야할지 감이 잘 오지 않는다. 따라서 먼저, 완전 탐색을 이용한 방법으로 푸는 방법을 알아보고자 한다.
import java.util.Scanner;
public class TofuCutSol209 {
// 두부가 선택되었는지 확인하기 위한 배열
public static int[][] chk = new int[20][20];
// 가격 배열, 풀이에서는 26x26배열이지만 이미 F가 마지막 배열이므로 26까지 필요 없다. 아래에서 A~F까지 알파벳에서 A를 빼서 배열 위치를
// 확인하고 있으므로 6x6을 지정해야 한다. 자바에서 배열 초기화 방법이 C와 다르므로 아래와 같이 초기화했다.
public static int[][] P = new int[][]{
{100,70,40,0,0,0}, {70,50,30,0,0,0}, {40,30,20,0,0,0},
{0,0,0,0,0,0}, {0,0,0,0,0,0}, {0,0,0,0,0}
};
//입력을 받기 위한 변수 선언
public static int n;
public static char[][] A = new char[20][20];
public static int max(int a, int b) {
return a > b ? a : b;
}
public static int f(int a, int 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;
// 만약 오른쪽 두부와 이어 2개 묶음을 만들 수 있다면
if (b+1<n && chk[a][b+1]==0) {
// 오른쪽 두부가 선택되었다고 체크하고
chk[a][b+1]=1;
// 현재 2개 두부의 가격과 한칸 오른쪽으로 옮겨 재귀 호출한 결과값 합한 것, 그리고 ans 중 큰 값을 ans에 할당
ans = max(ans, f(a,b+1)+P[A[a][b]-'A'][A[a][b+1]-'A']);
// 재귀함수에서 나왔을 때, 오른쪽 두부 선택한 것 해제
chk[a][b+1]=0;
}
// 만약 아래쪽 두부와 이어 2개 묶음을 만들 수 있다면
if(a+1<n && chk[a+1][b]==0){
// 아래쪽 두부가 선택되었다고 체크하고
chk[a+1][b]=1;
// 현재 2개 두부 가격과 오른쪽으로 한칸 옮겨 재귀호출한 결과값 합한 것, 그리고 ans 중 큰 값을 ans에 할당
ans=max(ans,f(a,b+1)+P[A[a][b]-'A'][A[a+1][b]-'A']);
// 재귀함수에서 나왔을 때, 아래쪽 두부 선택한 것 해제
chk[a+1][b]=0;
}
// 사용하지 않는 경우 다음 칸으로 옮겨 재귀호출한 결과 값과 ans 비교하여 최대값 선택
ans=max(ans, f(a,b+1));
// 현재 위치 두부 선택 해제
chk[a][b]=0;
}
현재 위치 두부가 이미 선택 되었다면
else
// 다음 칸으로 이동하여 재귀 함수 호출한 결과 값과 ans 비교하여 큰 값 ans로 할당
ans = max(ans, f(a,b+1));
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0; i < n; i++)
A[i]=sc.next().toCharArray();
sc.close();
System.out.println(f(0,0));
return;
}
}