공주님의 정원

오늘자 챌린지 문제로 나온 백준 2457번 공주님의 정원 문제이다

입력으로 꽃들이 주어지고 각각 꽃들의 피는 날짜와 지는 날짜가 주어진다

꽃들을 최소한으로 사용해서 3월 1일부터 11월 30일까지 매일 1개의 꽃이라도 피어있게 최소의 꽃들을 선택하는 것이 목표이다

풀이

실패한 풀이

예전에 라인 스위핑이라는 개념으로 백준 1931 회의실 배정이라는 문제를 푼 적이 있는데 이와 같은 개념으로 풀면 되지 않을까라고 생각했다

하지만 골드 3이라는 난이도에 걸맞게 생각을 좀 많이 해야 했고 날짜와 꽃을 구조체로 만들어 날짜를 비교하고 꽃을 비교하는 함수를 만들어서 꽃을 피는 순서로 정렬하고 반복문을 돌아가며 여러 경우의 수를 생각했다

틀린 코드를 보자

#include <bits/stdc++.h>

using namespace std;

int N;

struct Date
{
    int month;
    int day;
};

struct Flower
{
    Date start;
    Date end;
};

vector<Flower> flowers;

/// <summary>
/// 0 : equal
/// 1 : d1 < d2
/// -1 : d1 > d2
/// </summary>
int DateCompare(Date& d1, Date& d2)
{
    // 월 비교
    if (d1.month < d2.month)
    {
        return 1;
    }
    else if (d1.month > d2.month)
    {
        return -1;
    }
    else
    {
        if (d1.day < d2.day)
        {
            return 1;
        }
        else if (d1.day > d2.day)
        {
            return -1;
        }
        else
        {
            return 0;
        }
    }
}

bool FlowerCompare(Flower& f1, Flower& f2)
{
    int check = DateCompare(f1.start, f2.start);
    if (check == 1)
    {
        return true;
    }
    else if (check == -1)
    {
        return false;
    }
    else
    {
        check = DateCompare(f1.end, f2.end);
        
        if (check == 1)
            return true;
        else if (check == -1)
            return false;
        else
            return true;
    }
}

int answer;

int main()
{
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        if (a < 3 && c >= 3)
        {
            a = 3; b = 1;
        }

        Flower flower;
        flower.start = { a, b };
        flower.end = { c, d };

        flowers.push_back(flower);
    }

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

    for (int i = 0; i < N; i++)
    {
        cout << "(" << flowers[i].start.month << "," << flowers[i].start.day << ") ~ ";
        cout << "(" << flowers[i].end.month << "," << flowers[i].end.day << ")\n";
    }

    Date dateEnd;
    dateEnd.month = 11;
    dateEnd.day = 30;

    Flower prev = flowers[0];
    answer++;

    for (int i = 1; i < N; i++)
    {
        cout << i << " : ";

        if (DateCompare(prev.start, flowers[i].start) != -1 && DateCompare(prev.end, flowers[i].end) != 1)
        {
            cout << "이전 꽃 기간에 현재 꽃 기간이 포함됨";
        }
        else if (DateCompare(prev.start, flowers[i].start) != 1 && DateCompare(prev.end, flowers[i].end) != -1)
        {
            cout << "현재 꽃 기간에 이전 꽃 기간이 포함됨";
            prev = flowers[i];
        }
        else
        {
            // 꽃이 1개라도 피어있을때까지 날짜 < 다음 꽃이 피는 날짜면 -> 비는 날짜가 있으면
            if (DateCompare(prev.end, flowers[i].start) == 1)
            {
                cout << "비는 날짜가 존재\n";
                cout << 0;
                return 0;
            }
            else
            {
                cout << "직전 꽃 지는 날짜 > 현재 꽃 피는 날짜 -> 현재 꽃을 추가";
                answer++;
                prev = flowers[i];
            }
        }

        if (DateCompare(prev.end, dateEnd) <= 0)
        {
            break;
        }

        cout << '\n';
    }

    if (DateCompare(prev.end, dateEnd) == 1)
    {
        cout << 0;
    }
    else
    {
        cout << answer;
    }

    return 0;
}

/*
(2,15) ~ (3,23) 
(2,28) ~ (4,25) 
(4,12) ~ (6,5) 
(5,2) ~ (5,31) 
(6,3) ~ (6,15) 
(6,15) ~ (9,3) 
(6,15) ~ (9,27) 
(7,14) ~ (9,1) 
(9,14) ~ (12,24)
(10,5) ~ (12,31)
*/

예제 2번의 입력에 대한 답은 도출할 수 있지만 예제 1번의 입력에 대한 답은 도출할 수 없었다. 아무래도 날짜 하나씩 돌아가며 선택하는 것이 아닌 것 같음

수정한 풀이

지금 코드는 매우 복잡해 다른 사람이 보면 전혀 알아보지 못하는 코드이다

그래서 꽃이 피는 날짜와 꽃이 지는 날짜를 pair<int, int>가 아닌 하나의 숫자로 다뤄보자

월과 일을 입력하면 하나의 숫자로 표현해주는 함수를 만든다

처음 꽃을 입력받아서 알아서 예외 사항을 처리한다. 11월 30일 이후에 지는 꽃이 없거나 3월 1일부터 피는 꽃이 없거나하면 바로 프로그램을 종료한다

꽃의 피는 날짜로 오름차순 정렬하고 현재 날짜를 3월 1일로 하고 현재 날짜를 확장할 수 있는 꽃 중에서 가장 늦게 지는 꽃을 선택한다

꽃을 선택할 때마다 정답을 증가시키고 현재 날짜를 갱신한다. 만약 빈 공간이 생긴다면(현재 날짜와 선택 가능한 다음 꽃이 피는 날까지 공백이 생기면) 0을 반환한다

예제를 통해 알아보자

예제 2의 입력을 오름차순으로 정렬할 때 순서로 하겠다

2월 15일 ~ 3월 23일

현재 날짜인 3월 1일보다 일찍 피므로 최대 범위를 갱신할 수 있으면 갱신한다. 최대 날짜가 3월 23일이 된다

2월 28일 ~ 4월 25일

현재 날짜인 3월 1일보다 일찍 피므로 최대 범위를 갱신한다. max(3월 23일, 4월 25일)이므로 최대 날짜가 4월 25일로 갱신된다

4월 12일 ~ 6월 5일

현재 날짜인 3월 1일보다 늦게 피므로 최대 범위를 갱신하지 못한다. 꽃 개수를 증가시키고 현재 날짜를 4월 25일로 초기화한다

꽃 1개로 일단 3월 1일부터 4월 25일까지 커버할 수 있다

다시 현재 날짜인 4월 25일에서 최대 범위를 6월 5일로 설정한다

5월 2일 ~ 5월 31일

현재 날짜인 4월 25일보다 5월 2일이 늦기에 꽃 개수를 증가시키고 현재 날짜를 최대 범위인 6월 5일로 초기화한다

현재까지 선택된 꽃 : (2.28 ~ 4.15 / 4.12 ~ 6.5)

6월 3일 ~ 6월 15일

현재 날짜인 6월 5일보다 이전에 피기에 최대 범위를 6월 15일로 초기화한다

6월 15일 ~ 9월 3일

현재 날짜인 6월 3일 이후에 피기에 꽃을 추가하고 현재 날짜를 6월 15일로 초기화한다

현재까지 선택된 꽃 : (2.28 ~ 4.15 / 4.12 ~ 6.5 / 6.3 ~ 6.15)

6월 15일 ~ 9월 27일

현재 날짜를 6월 15일 이후에 피기에 최대 범위를 9월 27일로 초기화한다

7월 14일 ~ 9월 1일

꽃의 개수를 증가시킨다. 현재 날짜를 9월 27일로 초기화

현재까지 선택된 꽃 : (2.28 ~ 4.15 / 4.12 ~ 6.5 / 6.3 ~ 6.15 / 6.15 ~ 9.27)

9월 14일 ~ 12월 24일

현재 날짜보다 일찍 피므로 최대 범위를 12월 24일로 초기화

10월 5일 ~ 12월 31일

현재 날짜보다 늦게 피므로 현재 날짜를 12월 24일로 초기화하고 꽃 개수 증가

현재까지 선택된 꽃 : (2.28 ~ 4.15 / 4.12 ~ 6.5 / 6.3 ~ 6.15 / 6.15 ~ 9.27 / 9.14 ~ 12.24)

현재 날짜가 11월 30일 이후이므로 꽃 개수를 출력하고 프로그램 종료

정리

현재 날짜에서 최대한 늦게 지는 꽃을 선택해가며 문제를 푸는 그리디 방식이다

구간을 확장해나가고 빈 구간이 없도록 하는 것이 포인트

지금 말고 나중에 한번 더 풀면 코드를 올리도록 하겠다