[BOJ/백준][Gold4] 2457 : 공주님의 정원 (C++)

www.acmicpc.net/problem/2457  

2457번: 공주님의 정원

 

[난이도] Gold4

[유형] Greedy

 

[풀이]

pair vector를 만들어서 first에 꽃이 피는날 second에 꽃이 지는날을 저장 후 정렬.

0~N-1 루프를 돌면서 최적의 꽃을 찾아주면 된다.

코드에서 s는 현재까지 꽃이 무조건 피어있다고 보장되는 날이다.

first가 s이하인 꽃들 중에서 second가 가장 큰 값을 mxr에 갱신해서 찾는다.

first가 s를 넘어가게 되면 위의 mxr이 최대인 꽃을 선택하고 다음 꽃을 찾는다.

이 때, 꽃이 피어있다고 보장되는나 s는 mxr로 갱신시킨다.

위의 과정을 반복하면 된다.

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[] = {0,31,28,31,30,31,30,31,31,30,31,30,31},base[13];
int N,ans;
vector<pair<int,int>> v;
int main(){
    for(int i=1;i<=12;i++) base[i]=a[i-1]+base[i-1];
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int b[4];
        for(int j=0;j<4;j++) scanf("%d",&b[j]);
        v.push_back({base[b[0]]+b[1],base[b[2]]+b[3]});
    }
    sort(v.begin(),v.end());

    int s=base[3]+1,e=base[11]+30,mxr=-1,ok=0;
    for(int i=0;i<N;i++){
        auto p = v[i];
        int l=p.first,r=p.second;
        if(l<=s) {
            mxr=max(r,mxr);
            if(mxr > e){
                ok=1;
                ans++;
                break;
            }
        }
        else {
            if(mxr==-1) break;
            ans++;
            s=mxr;
            mxr=-1;
            i--;
        }
    }
    printf("%d",ok?ans:0);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2457.cpp