한빛 알고리즘 chapter8 동적프로그래밍 조약돌놓기 문제

조약돌놓기 문제에서 서로 양립할 수 없는 패턴들에 대한 부분이 문제가 확장된다면 변경이 필요하겠네요....

일단 책 기준으로해서 작성합니다...


----------------------------------------------------------------------------------------------------------

public interface Pebble {


public int pebble(int[][] dataA, int[][] resultA, int col, int pattern);

}


public interface PebbleBottomUp {


public int pebble(int[][] dataA, int[][] resultA);


}

----------------------------------------------------------------------------------------------------------
//Top Down(Recursive)방식 
public class DonghunPebble implements Pebble {

//양립할 수 있는 패턴정보 배열 (문제의 row값이 변경이 되면 동적으로 변경할 필요있음)
static int[][] availablePattern = {
{1,2}, //0번 패턴  (1,2 패턴 양립가능)
{0,2,3}, //1번 패턴  (0,2,3 패턴 양립가능)
{0,1}, //2번 패턴  (2 패턴 양립 가능)
{1} //3번 패턴  (1 패턴 양립가능)
};
@Override
public int pebble(int[][] dataA, int[][] resultA, int col, int pattern) {

int result = Integer.MIN_VALUE;
if(col == 0){
result = w(dataA, col, pattern);
}else{
//양립할 수 있는 패턴 추출
int[] q = availablePattern[pattern];
int tmp = 0;
for(int i=0; i < q.length; i++){
tmp = pebble(dataA, resultA, col-1, q[i]) +  w(dataA, col, pattern);
if(tmp > result){
result = tmp;
}
}
}
resultA[col][pattern] = result;//결과 검증용으로 중간단계 결과들 저장
return result;
}
private int w(int[][] dataA, int i, int p){
switch(p){
case 0:
return dataA[0][i];
case 1:
return dataA[1][i];
case 2:
return dataA[2][i];
case 3:
default:
return dataA[0][i] + dataA[2][i];
}
}
}
----------------------------------------------------------------------------------------------------------------------
//Bottom Up방식 
public class DonghunPebbleBottomUp implements PebbleBottomUp {

//양립할 수 있는 패턴정보 배열 (문제의 row값이 변경이 되면 동적으로 변경할 필요있음)
static int[][] availablePattern = {
{1,2}, //0번 패턴  (1,2 패턴 양립가능)
{0,2,3}, //1번 패턴  (0,2,3 패턴 양립가능)
{0,1}, //2번 패턴  (2 패턴 양립 가능)
{1} //3번 패턴  (1 패턴 양립가능)
};

@Override
public int pebble(int[][] dataA, int[][] resultA) {

//첫번째 열 데이터 설정
for(int p=0; p < 4; p++){
resultA[0][p] = w(dataA, 0, p);
}
int tmp = 0;
int result = 0; 
for(int i=1; i < dataA[0].length; i++){
result = Integer.MIN_VALUE;
for(int p=0; p < 4; p++){
//p와 양립하는 패턴 q
int[] q = availablePattern[p];
tmp = maxPreviosValue(resultA, i-1, q) + w(dataA, i, p);
resultA[i][p] = tmp;//결과저장
if(tmp > result){
result = tmp;
}
}
}
return result;
}
private int maxPreviosValue(int[][] resultA, int col, int[] q){
int result = Integer.MIN_VALUE;
int tmp = 0;
for(int k=0; k < q.length; k++){
tmp = resultA[col][q[k]];
if(tmp > result){
result = tmp;
}
}
return result;
}
private int w(int[][] dataA, int i, int p){
switch(p){
case 0:
return dataA[0][i];
case 1:
return dataA[1][i];
case 2:
return dataA[2][i];
case 3:
default:
return dataA[0][i] + dataA[2][i];
}
}


}
-----------------------------------------------------------------------------------------------------------------------
//Test Code
public class DonghunPebbleTest {

static int[][] dataA = {
{ 6,  7, 12, -5, 5,  3, 11, 3},
{-8, 10, 14,  9, 7, 13,  8, 5},
{11, 12,  7,  4, 8, -2,  9, 4}
};

@Test
public void testPebble(){
int[][] resultA = new int[8][4];//7개 열의 데이터, 4개 패턴 결과 용
int result = Integer.MIN_VALUE;
int tmp = 0;
Pebble pebble = new DonghunPebble();
for(int p=0; p < 4; p++){
tmp = pebble.pebble(dataA, resultA, 7, p);
if(tmp > result){
result = tmp;
}
}
System.out.println("result=" + result);
Assert.assertEquals(106, result);
print(resultA);
}
@Test
public void testPebbleBottomUp(){
int[][] resultA = new int[8][4];//7개 열의 데이터, 4개 패턴 결과 용
int result = Integer.MIN_VALUE;
PebbleBottomUp pebble = new DonghunPebbleBottomUp();
result = pebble.pebble(dataA, resultA);
System.out.println("result=" + result);
Assert.assertEquals(106, result);
print(resultA);
}
private void print(int[][] data){
for(int i=0; i < data.length; i++){
for(int j=0; j < data[0].length; j++){
System.out.print(data[i][j] + " ");
}
System.out.print("\n");
}
}
}