링크

2457 공주님의 정원

문제

풀이

이 문제는 그리디 문제이다.

시간초과의 늪에서 빠져나오질 못해서 다른 사람들의 블로그를 참고했다.(87%쯤에서 계속 시간초과걸림)

일단 풀이 방법은 예전에 회의실배정과 같은 문제와 비슷해서 생각보다는 쉽게 접근했다.
1. start를 기준으로 오름차순하고 end를 기준으로 내림차순 한다.
2. 그리고 조건이 까다로운데 하나하나 체크해봐야 된다.

• 시작일이 3월 1일이고 끝나는일이 12월 1일이다.
• 하나하나 꺼내가면서 현재 꺼낸 요소가 이전에 꺼냈던 마지막일보다 작거나 같아야 된다.(이 조건이 있어야 꽃이 항상 존재한다)
• 만약 12월 1일이 벗어나면 탐색을 안해도 된다.
• 12월 1일까지 꽃이 항상 피지 않는다면 0을 출력해야 한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Node implements Comparable<Node>{
    int startDate;
    int endDate;

    public Node(int startDate, int endDate){
        this.startDate = startDate;
        this.endDate = endDate;
    }


    @Override
    public int compareTo(Node node){
        if(node.startDate == this.startDate){
            return node.endDate - this.endDate;
        }


        return this.startDate - node.startDate;
    }
}

public class Main{
    public static List<Node> list = new ArrayList<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            int start = a * 100 + b;
            int end = c * 100 + d;


            list.add(new Node(start, end));
        }

        Collections.sort(list);

        //3월 1일부터 ~ 11월 30일
//        for(Node node : list){
//            System.out.println("start = " + node.startDate + ", end = " + node.endDate);
//        }

        int start = 301;
        int totalEnd = 0;
        int flower = 0;
        int idx = 0;

        while(start < 1201){
            boolean addFlower = false;
//            System.out.println("start = " + start);
//            System.out.println("totalEnd = " + totalEnd);
//            System.out.println("idx = " + idx);
            for(int i=idx;i<list.size();i++) {
//                if(list.get(i).startDate > start) break;

//                System.out.println("i = " + i + ", startDAte = " + list.get(i).startDate + ", endDate = " + list.get(i).endDate);
                if(list.get(i).startDate <= start && totalEnd < list.get(i).endDate){
                    totalEnd = list.get(i).endDate;
                    idx = i + 1;
                    addFlower = true;
//                    System.out.println("startDate = " + list.get(i).startDate + " endDate = " + list.get(i).endDate);
                }

            }
//            System.out.println();

            start = totalEnd;

            if(addFlower){
                flower++;
            } else{
                break;
            }


        }

        if(start < 1201) System.out.println(0);
        else System.out.println(flower);

    }

}```