백준 2457-공주님의 정원 (greedy)

문제 : 2457번: 공주님의 정원 (acmicpc.net)

2457번: 공주님의 정원

각 꽃들의 피어있는 날짜가 주어지고, 최대한 적은 꽃들을 선택해서

3월1일 ~ 11월30일 까지 피어있게 하는 문제입니다.

 

풀이과정

회의실 배정 문제와 비슷하지만 날짜를 처리하는 방법을 생각하는 데 어려움을 겪었습니다.

 

* 다른 블로그를 참고해서 찾은 방법으로 vector에 그냥 넣지 않고 3월 1일 이면

3*100 + 1 이런식으로 넣는 방법이 있었고, 이를 활용했습니다.

 

* 그리디하게 접근하기 위해 꽃이 피기 시작하는 순서대로 오름차순 정렬을 해줬고,

만약 피는 시기가 같다면 꽃이 지는 순서대로 오름차순 정렬을 했습니다.

 

* date 변수를 둬서 초기값으로 301로 두고 "꽃이 피기 시작한 날짜" 를 계속해서 업데이트 했습니다.

while문을 통해 date가 1130을 초과하지 않고 꽃의 index가 끝에 도달하지 않을동안 반복하는데,

 

1. 현재 꽃 ~ 마지막 꽃 중에 date보다 더 꽃이 빨리 피면서 가장 느리게 지는 꽃을 찾습니다.

2-1. 만약 꽃을 선택했다면 date를 해당 꽃의 시작점으로 업데이트 합니다.

2-2. 만약 꽃이 선택되지 못했다면 답을 찾을 수 없다는 뜻이기 때문에 종료합니다.

 

이런 순서로 반복하면 되겠습니다.

마지막까지 시도해서 while문 탈출에 성공했더라도 date가 1130 이하라면 답을 찾을 수 없으므로

한번 더 조건문을 달았습니다.

 

코드

#include <iostream>
#include <vector>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
int N;
// 3.1 ~ 11.30
// 가능한 적게
typedef struct option {
    int starts,ends;
}op;
vector < op > v;

bool cmp(const op &a, const op &b) {
    if(a.starts < b.starts) return true;
    else if(a.starts == b.starts) {
        if(a.ends < b.ends) return true;
    }
    return false;
}

int solution() {
    int date = 301;
    int j = -1;
    int answer = 0;
    // 꽃을 선택했는지 여부
    while(date <= 1130 && j < N-1) {
        bool flag = false;
        j++;
        // 새로운 시작점
        int newDate = 0;
        for(int i=j; i<N; i++) {
            // 시작 date가 더 늦다면 패스
            if(date < v[i].starts) break;
            // 시작 date보다 빠르면서 가장 늦게 끝나는 date 꽃 잦기
            if(newDate < v[i].ends) {
                j = i;
                newDate = v[i].ends;
                flag = true;
            }
        }
        // 꽃을 선택했다면
        if(flag == true) {
            answer++;
            date = newDate;
        }
        // 꽃을 선택하지 못했다면 답을 찾을수없음
        else return 0;
    }
    if(date <= 1130) return 0;
    else return answer;
}

int main()
{
    int a,b,c,d;
    scanf("%d",&N);
    for(int i=0; i<N; i++) {
        scanf("%d %d %d %d",&a,&b,&c,&d);
        v.push_back({a*100+b, c*100+d});
    }
    sort(v.begin(),v.end(),cmp);
    printf("%d\n",solution());
}