오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.
총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)
이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.
공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다.
N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오.
우선 문제를 풀기 전에 std라는 것에 대해 알게 되었고 std::sort의 사용법을 알아보았다. std::sort는 몇 줄 만에 O(nlog(n)) 시간 복잡도의 정렬 알고리즘을 구현 할 수 있게 도와준다. 몹시 편리하다.
공주님의 정원은 처음 문제를 보면 모든 경우의 수를 다 구한 뒤 최적의 답을 골라야 할 것 같지만 사실은 선택했을 때 무조건 이득이 되는 꽃이 존재한다. 그러므로 우선 꽃이 피는 시기로 오름차순 정렬을 한 뒤 3월 1일 보다 빨리 피는 꽃들 중 가장 늦게 지는 꽃을 기준으로 다시 빨리 피는 꽃들을 구하며 이 과정을 반복한 뒤 11월 30일이후에 꽃이 지게 되면 꽃의 개수를 출력한다. 만약 12월 이전에 꽃이 모두 지게 되면 0을 출력한다.
#include #include using namespace std; struct aa{ int sm,sd,em,ed; }map[100005],Max; bool opfs(aa a, aa b) { if (a.sm == b.sm) { if (a.sd == b.sd) { if (a.em == b.em) { return a.ed > b.ed; } return a.em > b.em; } return a.sd < b.sd; } return a.sm < b.sm; } bool opsd(aa a, aa b) { if (a.em == b.em) { return a.ed < b.ed; } return a.em < b.em; } int n,i,nm,nd,ch,cnt,j,e; int main() { scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d%d%d%d", &map[i].sm, &map[i].sd, &map[i].em, &map[i].ed); } nm = 3; nd = 1; std::sort(map,map+n,opfs); e = 0; while(1) { ch = nm*100+nd; /* for (i = 0; i < n; i++) { printf("%d %d %d %d\n",map[i].sm,map[i].sd,map[i].em,map[i].ed); } printf("\n"); */ for (i = e; i < n; i++) { if (map[i].sm < nm || (map[i].sm == nm && map[i].sd <= nd)) { if (Max.em < map[i].em || (Max.em == map[i].em && Max.ed <= nd)) { Max.em = map[i].em; Max.ed = map[i].ed; } } else { break; } } /* for (j = 0; j < n; j++) { printf("%d %d %d %d\n",map[j].sm,map[j].sd,map[j].em,map[j].ed); } printf("\n"); */ nm = Max.em; nd = Max.ed; e = i; cnt++; // printf("%d %d %d\n\n", nm, nd, e); if (nm*100+nd <= ch) { printf("0"); break; } if ((nm == 11 && nd == 30) || nm == 12) { printf("%d", cnt); break; } } return 0; }