[BOJ 2457] 공주님의 정원(C++)

공주님의 정원(Gold 4)

문제

전체 문제 보기

2457번: 공주님의 정원

접근법

이번 문제는 주어진 날짜 형식(mm dd)을 정수형으로 변환한 후 그리디로 풀 수 있는 문제입니다. 먼저 날짜를 정수형으로 변환하는 방법에 대해서 살펴봅니다.

날짜 형식을 정수형으로 변환

constexpr int monToInt[13] = { 0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334 };
int DayToInt(int mm, int dd)
{
    int retval{};
    retval += monToInt[mm];
    retval += dd;
    return retval;
}

각 월 마다 지난달들의 누적 합을 가지고 있는 배열 monToInt[]를 활용하여 mm dd 형식을 쉽게 정수형으로 변환할 수 있습니다. 예를 들어 2월 1일은 1월의 31 + 1로 총 32일이 됩니다. 6월 10일은 1월 1일 ~ 5월 31일까지의 총날짜인 151일 + 10일 = 161일이 됩니다.

Flower 구조체

이렇게 정수로 변환된 날짜를 담을 구조체 Flower를 다음과 같이 정의합니다. 그리디로 문제를 풀기 위해서는 꽃들을 정렬해야합니다. sort 함수에서 사용될 operator< 연산자를 함께 정의합니다. 시작 날짜를 기준으로 오름차순 정렬합니다.

struct Flower {
    int begin{};
    int end{};
    bool operator<(const Flower& other)
    {
        if (begin < other.begin) return true;
        else if (begin == other.begin) return end < other.end;

        return false;
    }
};

그리디

꽃을 가장 적게 심기 위해서는 가장 오랫동안 피어있을 꽃을 우선적으로 그리디 하게 선택해야 합니다. 그래서 먼저 꽃이 펴는 시점을 기준으로 정렬을 한 후 "이전 꽃이 지기 전에 피는 꽃들 중 가장 늦게 지는 꽃"을 탐색합니다. 이렇게 선택한 꽃이 11월 30일 이후에 질 때까지 반복합니다.

 

만약 위 조건에 맞는 꽃이 없는 경우 정원을 만들 수 없기 때문에 0을 출력합니다. 이를 위해서 bValid 라는 플래그 변수를 사용하였습니다. (저는 처음에 이 부분에 대한 예외처리를 하지 않아서 94% 대에서 시간 초과가 발생하였습니다.)

전체 구현

#include <iostream>
#include <vector>
#include <algorithm>
constexpr int monToInt[13] = { 0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334 };

int DayToInt(int mm, int dd)
{
    int retval{};
    retval += monToInt[mm];
    retval += dd;
    return retval;
}

struct Flower {
    int begin{};
    int end{};
    bool operator<(const Flower& other)
    {
        if (begin < other.begin) return true;
        else if (begin == other.begin) return end < other.end;

        return false;
    }
};
int main()
{
    //입출력 성능향상을 위한 설정
    std::ios_base::sync_with_stdio(false);
    std::cout.tie(NULL);
    std::cin.tie(NULL);

    int N; // N(1 ≤ N ≤ 100, 000)
    std::cin >> N;
    std::vector<Flower> flowers(N);
    for (int i = 0; i < N; ++i)
    {
        int mm, dd;
        std::cin >> mm >> dd;
        flowers[i].begin = DayToInt(mm, dd);
        std::cin >> mm >> dd;
        flowers[i].end = DayToInt(mm, dd);
    }
    sort(flowers.begin(), flowers.end());

    // 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록

    int answer{};
    int cur{};
    cur = DayToInt(3, 1);

    int i = 0;
    while (cur <= DayToInt(11, 30))
    {
        int prev = cur;
        bool bValid = false;
        for (; i < N && flowers[i].begin <= prev; i++)
        {
            if (cur < flowers[i].end)
            {
                cur = flowers[i].end;
                bValid = true;
            }
        }
        if (bValid == false)
        {
            answer = 0;
            break;
        }
        answer++;
    }
    std::cout << answer << '\n';
}

결과