2457

월과 일로 표현되어있는 날짜 단위를 하나로 통합한 후에 문제를 풀어야 한다.

나는 월/일을 모두 일로 바꿔서 계산했다. 이게 가장 쉬운 방법인것 같다.

나머지는 회의실 배정 문제와 비슷하다.

현재 꽃이 지기 전에 먼저 피어있는 꽃 들중에서 가장 늦게 지는 꽃을 고르면 된다.

여기서는 범위가 주어진다는 점 (3/1~11/30)과

문제의 조건에서 꽃이 지는 날은 꽃이 폈다고 볼 수 없다는 조건에 유의해서 문제를 풀면된다

O(N)에 해결하기 위해 sorting한 후 알고리즘을 적용했다.

#include<iostream> #include<cstdio> #include<algorithm> #include<vector> using namespace std; int days[13]={0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; struct Node{ int start, end; }; bool compare(Node a, Node b){ return a.start < b.start; } Node data[100005]; int main(){ int N; int from_m, from_d; int to_m, to_d; scanf("%d", &N); for(int i=0; i<N; i++){ scanf("%d %d %d %d", &from_m, &from_d, &to_m, &to_d); int store_start=0, store_end=0; for(int piv=1; piv<from_m; piv++) store_start += days[piv]; for(int piv=1; piv<to_m; piv++) store_end += days[piv]; store_start+=from_d; store_end += to_d; data[i].start=store_start; data[i].end=store_end; } sort(data, data+N, compare); int from=60; int to=334; vector<Node> sto; int piv = -1; while(1){ vector<int> nominees; int cur_end; cur_end = (piv==-1? from : data[piv].end); if(cur_end > to) break; for(int find=piv+1; find<N; find++){ if(data[find].start > cur_end) break; if(data[find].start<=cur_end && data[find].end > cur_end) nominees.push_back(find); } if(nominees.empty()){ printf("0\n"); return 0; } int find_nominee=0; for(int i=0; i<nominees.size(); i++){ if(data[nominees[i]].end > data[nominees[find_nominee]].end) find_nominee=i; } sto.push_back(data[nominees[find_nominee]]); piv=nominees[find_nominee]; } printf("%d\n", sto.size()); return 0; }