[백준 - 2457] 골드4 - 공주님의 정원(그리디)

www.acmicpc.net/problem/2457

2457번: 공주님의 정원

 

1. 유형

그리디, 정렬

 

2. 풀이

 

날짜를 숫자로 바꿔야 한다. (월*100 + 일)을 하면 11월 1일은 1101 이란 숫자로 변환된다.

 

이렇게 수를 구하고 클래스를 사용하여 월 기준 오름차순, 일 기준 오름차순으로 정렬

 

처음에 "시작 날짜가" 301 이하인것 중에서 "끝 날짜"가 가장 최대인 값을 구하는 식이다. 

 

java를 사용할 경우 100%에서 시간초과가 날 수 있다.

 

이때 가지치기를 잘 해야한다.

 

3. 코드

package 그리디;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Back_2457공주님의정원 {
	static class Pair implements Comparable<Pair> {
		int d1, d2;
		public Pair(int d1, int d2) {
			this.d1 = d1;
			this.d2 = d2;
		}
		@Override
		public int compareTo(Pair o) {
			if(this.d1 == o.d1) {
				return this.d2 - o.d2;
			}
			return this.d1 - o.d1;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		int n = Integer.valueOf(st.nextToken());
		ArrayList<Pair> list = new ArrayList<>();
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(in.readLine()," ");
			list.add(new Pair(Integer.valueOf(st.nextToken())*100+Integer.valueOf(st.nextToken()),
					Integer.valueOf(st.nextToken())*100+Integer.valueOf(st.nextToken())));		
		}
		Collections.sort(list);
		int ans=0;
		int fidx=0;
		int start=301;
		int max=0;
		while(start<1201) {
			max=0;
			boolean flag =false;
			for(int i=fidx;i<n;i++) {
				Pair cur= list.get(i);
				if(cur.d1 > start) break;
				if(cur.d1 <= start && max<cur.d2) {
					max = cur.d2;
					fidx=i+1;
					flag = true;
				}
			}
			if(flag) {
				start=max;
				ans++;
			}else
				break;
		}
		if(max<1201)
			System.out.println(0);
		else
			System.out.println(ans);
	}
}
//3자리 숫자로 바꾸기
//301이하에서 끝이 가장 큰값을 찾기

 

가지치기 - 만약 원하는 값을 구하지 못 한경우 뒤를 더 볼 필요가 없으므로 반복문 탈출

			if(flag) {
				start=max;
				ans++;
			}else
				break;