CLEARSKYPROJECT 관련 질문입니다.

  • tkagksmsen
    tkagksmsen

    안녕하세요

    CLEARSKYPROJECT를 푸는 도중에 오답이 떠서 어떠한 케이스가 비어있는지 스스로 체크가 힘들어 이렇게 글을 쓰게 되었습니다.

    먼제 제가 푼 방식은 Sort 이후 동적계획법을 이용하여

    D[k][n] = last{D[k - 1][0] ~ D[k - 1][n]} + xPos * 구름수

    형식의 테이블을 만들고, 위의 테이블에 k번째에 0~n까지 터트릴 수 있는 경우의 비용을 누적하여 테이블을 만들었습니다.

    그리고 여러 케이스를 손으로 그린 후 소스로 돌려 테스트해봤는데 혼자서는 도저히 오답이 나는 이유를 찾을 수가 없어서 도움을 받고자 이렇게 글을 쓰게 되었습니다.

    부탁드립니다. 오답 케이스좀 찾아주세요 ㅠ.ㅠ

    import java.util.Scanner;


public class Main {

    int k, n;
    int[][] cloude;
    int[][] cache;
    int totalXpos = 10000;
    int INF;

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

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

        int cnt = scn.nextInt();
        for(int i = 0; i < cnt; i++) {
            input(scn);
            sort();
            makeCache();
            //printCache();
            System.out.println(cache[k - 1][n - 1]);
        }

        scn.close();
    }

    public void input(Scanner scn) {
        n = scn.nextInt();
        k = scn.nextInt();

        cloude = new int[n][2];
        cache = new int[k + 1][n + 1];
        INF = k * totalXpos * 2;

        for(int i = 0; i < n; i++) {
            cloude[i][0] = scn.nextInt();
            cloude[i][1] = scn.nextInt();
        }
    }

    public void sort() {
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                if(cloude[i][0] > cloude[j][0]) {
                    int temp0 = cloude[i][0];
                    int temp1 = cloude[i][1];

                    cloude[i][0] = cloude[j][0];
                    cloude[i][1] = cloude[j][1];

                    cloude[j][0] = temp0;
                    cloude[j][1] = temp1;
                }
            }
        }

    }

    public void makeCache() {
        for(int i = 0; i < n; i++) {
            boolean flag = true;
            int remainedCloudeCnt = 0;
            //초기화
            for(int j = 0; j <= i; j++) {

                if( (cloude[i][0] <= cloude[j][0] && cloude[i][1] >= cloude[j][0]) || 
                    (cloude[i][0] <= cloude[j][1] && cloude[i][1] >= cloude[j][1]))
                    remainedCloudeCnt++;
                else flag = false;
            }

            if(flag) 
                cache[0][i] = cloude[i][0] * remainedCloudeCnt;
            else 
                cache[0][i] = INF;
        }

        for(int i = 1; i < k; i++) {
            for(int j = 0; j < n; j++)
                cache[i][j] = cache[i - 1][j];
            for(int j = 0; j < n; j++) {
                int last = -1;

                //이전 단계에 없어진 마지막 구름을 찾아서
                for(int check = j - 1; check >= 0; check--) {
                    if(cache[i - 1][check] != INF) {
                        last = check;
                        break;
                    }
                }



                boolean flag = true;

                while(flag && last >= 0) {
                    int remainedCloudeCnt = 0;

                    //나머지 구름을 다 없엘 수 있나 확인
                    for(int check = j; check > last; check--) {
                        if( (cloude[j][0] <= cloude[check][0] && cloude[j][1] >= cloude[check][0]) || 
                            (cloude[j][0] <= cloude[check][1] && cloude[j][1] >= cloude[check][1]))
                            remainedCloudeCnt++;
                        else flag = false;
                    }

                    //없엘 수 있으면 계산
                    if(flag) 
                        cache[i][j] = 
                            Math.min(
                                        cache[i][j], 
                                        (last == -1 ? 0 : cache[i - 1][last]) +  cloude[j][0] * (remainedCloudeCnt)
                                    );
                    last--;
                }
            }

        }

    }


    //cache 검증용
    public void printCache() {
        for(int i = 0; i < cache.length; i++) {
            for(int j = 0; j < cache[i].length; j++)
                System.out.print(cache[i][j] + " ");
            System.out.println();
        }
    }

}


    9년 전
0개의 댓글이 있습니다.

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