Baekjoon 2457번 공주님의 정원

문제

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

걸린 시간

01 : 02 : 17

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int date2day(int month, int day){
    int d = day;
    for(int m = 1; m <= month-1; m++){
        if(m == 2) d += 28;
        else if(m == 4 || m == 6 || m == 9 || m == 11) d += 30;
        else d += 31;
    }
    return d;
}

int main(){
    fastio;
    vector<int> day(date2day(12, 31)+1, 0);
    for(int d = date2day(3, 1); d <= date2day(11, 30); d++) day[d] = 1;
    int n;
    cin >> n;
    vector<pair<int, int>> f;
    int sm, sd, em, ed;
    for(int i = 0; i < n; i++){
        cin >> sm >> sd >> em >> ed;
        f.push_back({date2day(sm, sd), date2day(em, ed)-1});
    }
    int ans = 0;
    for(int d = 1; d < day.size(); d++){
        if(day[d]){
            int m = 0;
            int c = -1;
            for(int i = 0; i < f.size(); i++){
                int s = f[i].first;
                int e = f[i].second;
                if(s <= d && d <= e){
                    if(m <= e-d){
                        c = i;
                        m = e-d;
                    }
                }
            }
            if(c == -1){
                cout << 0 << "\n";
                return 0;
            }
            d = f[c].second;
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}

구현 태그도 달아줘야 할 것 같은 느낌의 그리디 문제였다. 꽃이 피어있어야 하는 3월 1일 부터 11월 30일 까지 매일, 심을 수 있는 꽃을 확인한 후 없으면 0을 출력 후 종료, 있으면 꽃이 지는 날짜에서 현재 날짜를 뺀 값이 제일 큰 꽃을 선택하면 된다. 이미 지나간 꽃의 수명은 정답에 영향을 주지 않으므로 남은 수명이 긴 꽃을 고르는 것이 항상 최적해이다.