[백준] 2457번 공주님의 정원 (C)

출처

2011 지역본선 초등2

문제 주소

백준 2457번 공주님의 정원

2457번: 공주님의 정원

알고리즘

그리디

힌트

오늘 심을 수 있는 꽃중 가장 오래 심을 수 있는 꽃들을 선택한다.

풀이

흔한 그리디 알고리즘 문제라고 보면 된다. 날짜의 대소 관계만 확인하면 되기 때문에 날짜 처리에 대한 고민을 할 필요가 없다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

#include<iostream> #include<algorithm> using namespace std;   struct A{     int end,start;  };   A in[100000];     // 먼저 심을 수 있는 순서대로 정렬한다.  int cmp(A a, A b){     return a.start<b.start; }       int main(){     int n;          cin>>n;          for(int i=0;i<n;i++){ // 날짜간의 대소관계만 비교하면 되기 때문에 다음과 같이 처리 할 수 있다.          int a,b,c,d;         cin>>a>>b>>c>>d;                  in[i].start=a*100+b;         in[i].end=c*100+d;         }          sort(in,in+n,cmp);          int now=301,ans=0,index,max=0;     for(int i=0;i<=n-1;i++){           // 1번째 종료조건 : 목표 달성          if(now>1130)                 break;           // 오늘(now)을 포함하는 꽃들 중 가장 오래 심을 수 있는 꽃을 찾는다.          if(max<in[i].end&&in[i].start<=now){              index=i;             max=in[i].end;         }           // 오늘을 포함 하지 않는 꽃이 등장하면 오늘의 날짜를 바꿔주고 이 꽃을 다시 봐야 하기 때문에 i에 1을 빼준다.         if(in[i].start>now&&max!=0){                 now=in[index].end;             ans++;             i--;             max=0;         }           // 3번째 종료조건 : 모든 꽃들을 확인한 경우          else if(max!=0&&i==n-1){                 now=in[index].end;             ans++;         }           // 2번째 종료조건 : 꽃 밭이 비어있는 날이 생길 때              else if(max==0){               ans=0;             break;         }     }          if(now<=1130)  // 모든 꽃을 다 확인하였지만 목표를 달성하지 못한 경우가 있는지 확인한다.          ans=0;          cout<<ans; }

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 코드 업, algorithm, 알고리즘, 자료구조, 문제, 문제 풀이, 정올 해설