글 읽기 - [JAVA] 반례가 필요합니다.

sos0911 5년 전 0

처음에는 dp[i]의 정의를

'input[i]가 제일 위에 있을 때 쌓을 수 있는 종이의 최대 수' 라고 정의하고

들어오는 input을 정렬을 하는데 정렬 결과에서 뒤의 색종이가 앞의 색종이에 포함되게끔 정렬하는데, 서로 포함되지 않는 관계라면 sort를 하지 않고 그대로 놔 두는 식으로 정렬을 구현하고 LIS 알고리즘과 비슷하게 로직을 짜서 dp[i]를 구했더니 오답 처리가 되었습니다.

그래서 찾아본 뒤 dp[i]를

'input[i]가 제일 아래에 있을 때 쌓을 수 있는 종이의 최대 수' 라고 재정의하고

입력받을 때 input의 x가 y보다 무조건 크도록 바꾼 뒤 x에 대해 오름차순, x가 같으면 y에 대해 오름차순으로 정렬하고 LIS 알고리즘을 썼더니 맞았습니다.

원인은 정렬 순서에 있는 것 같은데

왜 틀렸는지를 잘 모르니 따라서 반례가 뭐가 있는지도 감이 잘 안 옵니다ㅠㅠ

아래는 오답 소스입니다.

import java.io.*;
import java.util.*;
class paper{
    int y, x;
    public paper(int y, int x){
        this.y = y;
        this.x = x;
    }
}
public class Main {
     // tc : O(NlogN + N^2)
    public static void main(String[] args) throws IOException{
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int Nofp = Integer.parseInt(br.readLine());
        paper[] input = new paper[Nofp]; // 0 - 
        int[] dp = new int[Nofp]; // 0 - 
        StringTokenizer st;
        for(int i = 0; i < Nofp; i++){
            st = new StringTokenizer(br.readLine());
            input[i] = new paper(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        // 상대적 크기 역순으로 정렬 
        // 결과가 =< 0이면 그대로 놓고 > 0 이면 바꿈 
        Arrays.sort(input, (paper p1, paper p2) -> ((p1.y <= p2.y && p1.x <= p2.x) || (p1.y <= p2.x && p1.x <= p2.y))? 1 : -1);
        for(int i = 0; i < Nofp; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++) // 색종이 i가 색종이 j에 포함되어야 함
                if((input[i].y <= input[j].y && input[i].x <= input[j].x) || (input[i].y <= input[j].x && input[i].x <= input[j].y))
                    dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        int max = -1;
        for(int i = 0; i < Nofp; i++)
            max = Math.max(max, dp[i]);
        System.out.println(max);
    }
}
// dp[i] : 가장 위에 있는 종이가 input[i]일때 최대 장수
// dp[i]의 초기세팅값은 자기 자신이므로 1

sos0911 5년 전 0

자문자답 하겠습니다.

스캐폴딩을 해봤더니 결론적으로 제가 짠 코드에서는 제가 원하는 대로 정렬이 되지를 않았습니다.

정렬 기준을 한꺼번에 두 개 이상을 적용해서 정렬해 버리면 제가 생각한 대로 색종이 크기에 대한 상대적 내림차순이 되지를 않더군요.

왜 그런지는 Arrays.sort()가 작동하는 원리를 알아야 하기에 파일을 뜯어봐야 하는데 거기까지는 안 해봤구,,

하여튼 정렬을 할 때는 비교해야 할 기준이 2개 이상이면 기준들 사이에 우선순위를 정해서 if문을 이용해 첫번째 기준이 같으면 두번째 기준으로 순서를 정하는 식으로 comparator를 구현하는 게 속 편하다는 교훈을 얻은 것 같습니다.

그래서

dp[i]를 가장 아래에 있는 종이가 input[i]일때 최대 장수 로 정의한다면

y, x 중에 y가 x보다 무조건 크게 둔 다음 y로 정렬, y가 같다면 x로 정렬하는 식으로 구현하는 게 맞습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[JAVA] 반례가 필요합니다.

sos0911 5년 전 0

sos0911 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말