안녕하세요

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

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

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

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

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

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

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

}

</spoiler>