BOOKTHIEF 관련 질문입니다.

  • tkagksmsen
    tkagksmsen

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

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

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

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

    확인 부탁드립니다.

    (__)

    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();
        }
    }
}


    10년 전
2개의 댓글이 있습니다.
  • Being
    Being

    Math.max 이외에 무엇을 넣어서 비교해 보신 건가요? 확신하는 것은 아닙니다만 저것 때문에 시간초과일 것 같지는 않고요, 다른 식을 세우는 바람에 테이블 갱신이 이루어지지 않아서 훨씬 빠르게 돌거나 하는 게 아닐까 싶습니다.


    10년 전 link
  • tkagksmsen
    tkagksmsen

    으.. 말씀하신 부분이 맞았어요..; 완전 다른 방향으로 생각해서 이 문제를 해결했습니다. 감사합니다 ^ㅡ^


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.