백준 2457 - 공주님의 정원

 

 

문제 설명

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

총 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일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

https://www.acmicpc.net/problem/2457

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

 

문제를 요약하면, 서로 다른 a~b까지 기간 동안 피어있는 꽃들이 있을 때, 이 꽃들을 적절히 선택하여 3월 1일부터 11월 30일까지 적어도 하나의 꽃이 피어있도록 하면서 최소한의 꽃을 선택하는 방법을 구하는 것이다.

 

해당 문제는 일종의 그리디로 생각할 수 있다.

시작부터 생각해 보면 3월 1일보다 일찍 피고 늦게 지는 꽃들 중 가장 늦게 지는 것을 고르는 것이 유리하다.

만약, 그러한 꽃을 골랐다고 가정했을 때 꽃이 지는 날을 end라고 해보자.

그럼 다음 꽃을 고르는 기준은 end보다 일찍 피면서 최대한 늦게 지는 꽃을 고르면 된다.

이러한 과정을 반복하다 11월 30일 이후에 지는 꽃을 고른다면 종료한다.

 

그렇다면, 이러한 논리가 맞으려면 꽃들이 정렬되어 있어야 한다.

꽃이 피는 날짜를 기준으로 정렬하되 가장 늦게 지는 것이 앞에 올 수 있게 해야 한다.

struct Flower
{
    Flower(int a, int b, int c, int d)
    {
        startDay = convert(a, b);
        endDay = convert(c, d);
    }

    int startDay;
    int endDay;

    bool operator < (const Flower& other)
    {
        if (startDay == other.startDay) return endDay > other.endDay;
        return startDay < other.startDay;
    }
};

날짜를 비교하는 것이 번거롭기 때문에 날짜를 0~365의 숫자로 변환하는 작업을 거쳐 정수를 비교하는 것이 간편하다.

vector<int> dm = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int convert(int a, int b)
{
    int result = 0;
    for (int i = 0; i < a-1; i++)
    {
        result += dm[i];
    }
    result += b;

    return result;
}

 

정렬이 완료되면 기준점보다 일찍 피며 늦게 지는 꽃들을 모두 고른 뒤, 가장 늦게 지는 꽃을 선택하면 된다.

선택된 꽃이 지는 날이 다음 기준점이 된다.

처음에는 3월 1일을 기준으로 고르면 된다.

만약, 선택 과정을 진행하다 다음과 같은 예외가 발생할 수 있다.

• 기준점보다 일찍 지는 꽃이 있을 경우
• 기준점보다 늦게 피는 꽃이 있을 경우
• 11월 30일보다 늦게 지는 꽃이 없을 경우

첫 번째의 경우, 기준점은 이전에 선택한 꽃이 지는 날이 되고 정렬에 의해 기준점보다 뒤에서 비교되는 꽃은 기준점이 되는 꽃보다 늦게 피는 꽃이다.

늦게 피는 꽃이 기준점보다 일찍 진다는 얘기는 비교되는 꽃이 기준점이 되는 꽃의 범위 안에 있는 꽃이 된다는 얘기이다.

따라서, 이 경우는 무시하면 된다.

 

두 번째의 경우, 기준점보다 늦게 피는 꽃이 있다면 그 뒤에 꽃들 역시 정렬에 의해 더 일찍 피는 꽃이 있을 수 없다.

따라서, 적어도 하나의 꽃이 피어있게 하는 조건을 충족할 수 없다.

 

마지막 경우 역시 기준을 충족하지 못하기 때문에 답을 0으로 처리한다.

 while(i < N)
{
    //이미 범위가 지나감
    if (flowers[i].endDay <= start)
    {
        i++; 
        continue;
    }

    //겹치지 않음
    if (start < flowers[i].startDay)
    {
        cout << 0;
        return 0;
    }

    vector<Flower> temp;
    while (i < N && flowers[i].startDay <= start)
    {
        temp.push_back(flowers[i++]);
    }

    sort(temp.begin(), temp.end(), cmp);

    if (!temp.empty())
    {
        ans++;
        start = temp[0].endDay;
        
        //마지막 날을 지남
        if (finalDay < temp[0].endDay) break;
    }
}

if (start <= finalDay) ans = 0;

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;

vector<int> dm = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int convert(int a, int b)
{
    int result = 0;
    for (int i = 0; i < a-1; i++)
    {
        result += dm[i];
    }
    result += b;

    return result;
}

struct Flower
{
    Flower(int a, int b, int c, int d)
    {
        startDay = convert(a, b);
        endDay = convert(c, d);
    }

    int startDay;
    int endDay;

    bool operator < (const Flower& other)
    {
        if (startDay == other.startDay) return endDay > other.endDay;
        return startDay < other.startDay;
    }
};

bool cmp(const Flower& lhs, const Flower& rhs)
{
    return lhs.endDay > rhs.endDay;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);

    cin >> N;
    vector<Flower> flowers;
    for (int i = 0; i < N; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        flowers.push_back({ a,b,c,d });
    }

    sort(flowers.begin(), flowers.end());

    int start = convert(3, 1);
    int end = 0;
    int finalDay = convert(11, 30);

    int ans = 0;
    int i = 0;

    while(i < N)
    {
        //이미 범위가 지나감
        if (flowers[i].endDay <= start)
        {
            i++; 
            continue;
        }

        //겹치지 않음
        if (start < flowers[i].startDay)
        {
            cout << 0;
            return 0;
        }

        vector<Flower> temp;
        while (i < N && flowers[i].startDay <= start)
        {
            temp.push_back(flowers[i++]);
        }

        sort(temp.begin(), temp.end(), cmp);

        if (!temp.empty())
        {
            ans++;

            //마지막 날을 지남
            start = temp[0].endDay;
            if (finalDay < temp[0].endDay) break;
        }
    }

    if (start <= finalDay) ans = 0;
    cout << ans;

    return 0;
}

---