[문제해결을 위한 창의적 알고리즘] 두부 자르기2 (고급, p207)

앞선 포스트에서는 완전 탐색으로 두부 자르기 문제를 푸는 방법에 대해 적어 보았다. 이번에는 동적 계획법으로 푸는 방법을 소개하고자 한다. 문제 해결을 위한 창의적 알고리즘 고급편의 가장 마지막에 있는 동적 계획법 문제이므로 난이도가 가장 높은 동적 계획법 문제로 보인다.

import java.util.Scanner;

public class TofuCutSol213 {

public static int cu(){

return 1<<n;

}

public static int rt(){

return 1<<(n-1);

}

public static int dn(){

return 1;

}

public static int M(){

return 1<<(n+1);

}

public static int[][] p = new int[][]{

{100,70, 40, 0},

{70, 50, 30, 0},

{40, 30, 20, 0},

{0, 0, 0, 0, 0}

};

public static int n;

public static int[][] tb = new int[12][12];

public static int[][][] m = new int[12][12][1<<13];

public static int max(int a, int b){

return a > b ? a : b;

}

public static int f(int x, int y, int s){

if (x==n)

return 0;

if (y==n)

return f(x+1, 0, s);

if (m[x][y][s]<=0){

if ((s&cu())<=0){

if (y+1<n && (s&rt())<=0)

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())<=0)

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];

}

public static void main(String[] args) {

int i, j;

char t;

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

for (i=0; i<n; i++){

String temp = sc.next();

for (j=0; j<n; j++){

t = temp.charAt(j);

// 위에서 가격 테이블을 6x6으로 선언하지 않고 4x4로 선언한 것을 처리하는 방법

tb[i][j]=(t=='F'? 3: t-'A');

}

}

sc.close();

System.out.println(f(0,0,0));

return;

}

}

Big O(n^3)  

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

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

출처: 한국정보올림피아드 (2006 전국 본선 고등부)