[문제해결을 위한 창의적 알고리즘] 두부 자르기 (고급, 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;

}

}

Big O(3^(n*n)) : 모든 두부에 대해 3가지 선택 옵션이 있으므로...

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/TofuCutSol209.java

문제해결을 위한 창의적 알고리즘 목록