[백준] 2457 공주님의 정원

1. 문제

www.acmicpc.net/problem/2457

2457번: 공주님의 정원

2. 접근방법

회의실 배정문제를 반대로 꼬은 문제

 

기본적인 풀이 개념은

우선 시작시간을 기준으로 정렬을 하고 시작시간이 같다면 끝시간이 빠른게 앞으로 정렬하고

 

현재 끝시간보다 시작시간이 작으면서

끝시간이 최댓값인 것을 선택하고

 

끝 시간이 11월 30일을 초과하면 종료 하면 된다.

 

첫 끝 시간은 3월 1일로 설정하면 된다.

 

 

 

 

3. 자바 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class G4_2457공주님의정원 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		ArrayList<Point> arr = new ArrayList<Point>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int a1 = Integer.parseInt(st.nextToken());
			int a2 = Integer.parseInt(st.nextToken());
			int b1 = Integer.parseInt(st.nextToken());
			int b2 = Integer.parseInt(st.nextToken());
			arr.add(new Point(a1 * 100 + a2, b1 * 100 + b2));
		}
		Collections.sort(arr, new Comparator<Point>() {
			@Override
			public int compare(Point o1, Point o2) {
				if (o1.x == o2.x)
					return o1.y - o2.y;
				return o1.x - o2.x;
			}
		});
		int last = 301;
		int lastidx = -1;
		int cnt = 0;
		gg: while (true) {
			int temp = last;
			int i = lastidx;
			boolean isget = false;
			while (true) {
				if (++i >= N) {
					if (!isget) {
						cnt = 0;
						break gg;
					}
					break;
				}
				if (arr.get(i).x > temp) {
					if (!isget) {
						cnt = 0;
						break gg;
					}
					break;
				}
				if (arr.get(i).y > last) {
					lastidx = i;
					last = arr.get(i).y;
					isget = true;
				}
			}
			cnt++;
			if (last >= 1201)
				break;
		}
		System.out.println(cnt);

	}
}

4. 마치며

회의실 배정을 조금 꼬았다는 건 알았는데

역시 그리디는 조금 어려운 것 같다.

그리디 많이 풀어보자