안녕하세요 이번에 BOOKTHIEF를 Java로 풀다가 궁금증이 생겨서 이렇게 문의를 드리게 되었습니다.

먼저 처음 푼 방식은 재귀로 완전탐색 형식의 값을 cache에 넣어 놓음으로써 메모이제이션을 f(x, value) = cache[x][value] 형태로 기록하여 속도를 향상시키려 하였으나 속도가 여의치 않아서

동적계획법 D[x][value] 형태로 변환하여 값을 구하였습니다만.. 저 마지막의 Math.max부분에서 타임오버가 나서

혹시 더 최적화를 할 수 있는 방법이나 다른 언어로 해야 한다는 등의 해결 방법을 알고 싶어서 이렇게 올리게 되었습니다.

확인 부탁드립니다.

(__)

~~~ java
import java.util.Scanner;

public class Bookthief {

int[][] data;
int[][] table;
int totalVolumn;
int bookKind;

public static void main(String[] args) {
    new Bookthief();
}

public Bookthief() {
    Scanner scn = new Scanner(System.in);

    int cnt = scn.nextInt();

    for(int i = 0; i < cnt; i++) {
        input(scn);
        fillTable();
        System.out.println(findMax());
    }

    scn.close();
}

public void input(Scanner scn) {
    bookKind = scn.nextInt();
    totalVolumn = scn.nextInt();

    data = new int[bookKind][3];
    table = new int[bookKind][totalVolumn + 1];

    for(int i = 0; i < bookKind; i++) {
        data[i][0] = scn.nextInt();
        data[i][1] = scn.nextInt();
        data[i][2] = scn.nextInt();
    }
}

public void fillTable() {
    int[] changed = new int[totalVolumn + 2];

    for(int i = 0; i <= data[0][2]; i++) {
        if(i * data[0][0] >= totalVolumn)
            break;
        table[0][i * data[0][0]] = data[0][1] * i;
    }

    for(int i = 1; i < bookKind; i++) {

        changed[0] = 0;
        int cnt = 1;

        for(int j = 1; j < table[i - 1].length; j++) {
            if(table[i - 1][j] != 0) {
                cnt++;
                changed[cnt] = j;
                table[i][j] = table[i - 1][j];
            }
        }

        for(int j = 0; j <=cnt; j++) {
            int checkPos = changed[j];
            for(int k = 1; k <= data[i][2]; k++) {
                int checkTarget = data[i][0] * k;
                int targetValue = table[i - 1][checkPos] + data[i][1] * k;

                if(checkPos + checkTarget >= table[i].length)
                    break;

                table[i][checkPos + checkTarget] 
                        = Math.max(table[i][checkPos + checkTarget],  targetValue); // <== Math.max 삽입시 타임오버

            }
        }
    }
}

public int findMax() {
    int max = 0;

    for(int i = 0; i < table[table.length - 1].length; i++)
        max = Math.max(max, table[table.length - 1][i]);

    return max;
}

public void print() {
    for(int i = 0; i < table.length; i++) {
        for(int j = 0; j < table[0].length; j++)
            System.out.print(table[i][j] + " ");
        System.out.println();
    }
}

}

</spoiler>