BOJ_2457_공주님의 정원 (Java)

[Gold III] 공주님의 정원 - 2457

문제 링크

성능 요약

메모리: 22040 KB, 시간: 268 ms

분류

그리디 알고리즘, 정렬

제출 일자

2025년 2월 19일 04:11:26

문제 설명

오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다.

N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다.

출력

첫째 줄에 선택한 꽃들의 최소 개수를 출력한다. 만약 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력한다.

문제 풀이

날짜를 정렬한다. 정렬 기준은 시작일을 오름차순, 끝일을 내림차순으로.

모든 날짜가 연속되도록 만들었다.

이후 선택을할건데 최대한 지금까지 한 구간이랑 한 날짜라도 겹쳐야하고 이후 뒤로 기간이 늘어야하므로 이걸 flag로 체크하면서 진행.

코드

코드 1

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    class Flower implements Comparable<Flower>{
        int start, end;
        public Flower(int start, int end){
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Flower o) {
            if(this.start == o.start) return o.end - this.end;
            return this.start - o.start;
        }
    }
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, START, END, res;
    static int[] monthPrefix = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30}; // 1~11월
    static Flower[] flowers;
    static boolean flag=true; // 가능하면 true
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2457_공주님의정원/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // m월 0일
        for(int i=1; i<monthPrefix.length; i++) {
            monthPrefix[i] += monthPrefix[i-1];
        }
//        System.out.println(Arrays.toString(monthPrefix));
        START = monthPrefix[2] + 1;
        END = monthPrefix[10] + 30;

        N = Integer.parseInt(br.readLine());
        flowers = new Flower[N];
        int m1, d1, m2, d2;
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            m1 = Integer.parseInt(st.nextToken());
            d1 = Integer.parseInt(st.nextToken());
            m2 = Integer.parseInt(st.nextToken());
            d2 = Integer.parseInt(st.nextToken());
            flowers[i] = new Flower(monthPrefix[m1-1] + d1, monthPrefix[m2-1] + d2);
        }

        Arrays.sort(flowers);

        int currEnd = START;
        int idx = 0;
        while(currEnd <= END && flag) {
            int nextEnd = currEnd;
            while(idx < N && flowers[idx].start <= currEnd){
                if(nextEnd < flowers[idx].end){
                    nextEnd = flowers[idx].end;
                }
                idx++;
            }

            // 발전이 없음
            if(nextEnd == currEnd) flag = false;
            else {
                res++;
                currEnd = nextEnd;
            }
        }
        System.out.println(flag? res : 0);
        bw.flush();
        bw.close();
        br.close();
    }
}

---

코드 2(빠른입출력)

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static class FastReader {
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[16384];
            bufferPointer = bytesRead = 0;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, buffer.length);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            return neg ? -ret : ret;
        }
    }
    class Flower implements Comparable<Flower>{
        int start, end;
        public Flower(int start, int end){
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Flower o) {
            if(this.start == o.start) return o.end - this.end;
            return this.start - o.start;
        }
    }
    static FastReader fr;
    static int N, START, END, res;
    static int[] monthPrefix = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30}; // 1~11월
    static Flower[] flowers;
    static boolean flag=true; // 가능하면 true
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        fr = new FastReader();

        // m월 0일
        for(int i=1; i<monthPrefix.length; i++) {
            monthPrefix[i] += monthPrefix[i-1];
        }
//        System.out.println(Arrays.toString(monthPrefix));
        START = monthPrefix[2] + 1;
        END = monthPrefix[10] + 30;

        N = fr.nextInt();
        flowers = new Flower[N];
        int m1, d1, m2, d2;
        for(int i=0; i<N; i++) {
            m1 = fr.nextInt();
            d1 = fr.nextInt();
            m2 = fr.nextInt();
            d2 = fr.nextInt();
            flowers[i] = new Flower(monthPrefix[m1-1] + d1, monthPrefix[m2-1] + d2);
        }

        Arrays.sort(flowers);

        int currEnd = START;
        int idx = 0;
        while(currEnd <= END && flag) {
            int nextEnd = currEnd;
            while(idx < N && flowers[idx].start <= currEnd){
                if(nextEnd < flowers[idx].end){
                    nextEnd = flowers[idx].end;
                }
                idx++;
            }

            // 발전이 없음
            if(nextEnd == currEnd) flag = false;
            else {
                res++;
                currEnd = nextEnd;
            }
        }
        System.out.print(flag? res : 0);
    }
}