글 읽기 - 반례 부탁드립니다!!

ybc125 2년 전 0

질문에 등장한 반례들은 다 맞습니다!

반례가 혹시 있을까요? 9%에서 틀립니다!

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Boj_2565 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 전깃줄 최소로 없애서 교차하지 않게 만들기
		// 1 <= 전깃줄 갯수 <=100, 1 <= 위치의 번호 <= 500 -> boolean 배열선언 최대 boolean[500][500]
		// boolean으로 해도 됨.
		// 같은 위치에 두 개 이상 전깃줄 X
		// 특정 전깃줄이 엮여 있는 갯수를 각각 넣어둬야 할까?
		// 정렬을 해보자

		int arr[][];
		int N;
		StringTokenizer stz;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N][3]; // 전깃줄 배열 저장
		int answer = 0;
		for (int i = 0; i < N; i++) {
			stz = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(stz.nextToken());
			int to = Integer.parseInt(stz.nextToken());
			arr[i] = new int[] { from, to, 0 };
		}
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0]; // o1, o2의 인덱스 들이가 같을 일이 없음
			}
		});

		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (arr[i][1] > arr[j][1]) { // 겹치는 횟수 저장
					arr[i][2]++;
					arr[j][2]++;
				}
			}
		}
/		
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o2[2] - o1[2]; // 겹치는 순으로 내림차순 배열 정렬
			}
		});


		for (int i = 0; i < N; i++) {
			if (arr[i][2] != 0) {
				answer++;


				for (int j = 0; j < N; j++) {
					if (((arr[i][1] > arr[j][1] && arr[i][0] < arr[j][0])
							|| (arr[i][1] < arr[j][1] && arr[i][0] > arr[j][0]))&& arr[i][2]!=0 && arr[j][2]!=0) { // 겹치는 횟수 저장
						arr[i][2]--;
						arr[j][2]--;
					}
				}
			}
		}

		System.out.println(answer);

	}
}

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

문제

문제

출처

ICPC

반례 부탁드립니다!!

ybc125 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말