2457. 공주님의 정원

https://www.acmicpc.net/problem/2457

2457번: 공주님의 정원

 

 

초등학교 6학년 때인가 풀었던 문제를 다시 풀어봤다.

그때는 나름 내게 어려웠던 문제라, 문제를 풀었을 때 되게 기뻤던 기억이 있다.

그리고 이 문제가 내가 c++ std class의 sort 함수를 응용해서 풀었던 첫 문제였다.

'공주님의 정원'은 가장 기억에 남았던 문제중 하나라, 이 문제를 내 백준 복귀? 기념으로 풀 문제로 선정하게 되었다.

 

문제 티어는 골드3 이다. 1시간 조금 안되게 걸린 것 같다.

 

/*

코딩할 때 원래 예전에 즐겨 사용하던 visual studio 2010을 설치하고 다시 써볼까 하는 생각도 했었는데,

이번 기회에 아예 vscode로 통일하고 싶었다.

MinGW를 설치한 후(gcc 컴파일러 설치), vscode에서 task.json, 실행 단축키 등의 설정을 해줬다.

 알아보고 하는데 거의 1시간 걸린듯 ㅜㅜ

*/

 

 

그리디 알고리즘을 사용하면 쉽게 해결할 수 있다.

그리디 알고리즘은 최적화된 해를 구하기 위해서, 매 단계마다 최선의 선택을 하는 알고리즘이다.

알고리즘에 관한 자세한 내용은 따로 카테고리를 만들어서 차곡차곡 하나씩 쌓아봐야겠다!

 

 

- 풀이 -

struct 구조체와 std::sort를 응용하여 해결하였다.

 

꽃이 피는 날짜와 지는 날짜를 임시 변수에 입력 받고 각각 1월 1일을 기준으로 떨어진 일 수를 계산하여, 그 값을 각각 flowers[i].start 와 flowers[i].end에 저장하였다.

 

그리고 std::sort를 활용해 꽃이 피는 날짜를 기준으로 정렬해 주었다.

 

그 후 이중 while 문을 활용해 그리디 알고리즘으로 최소로 필요한 꽃의 수를 구해주었다.

 

#include<stdio.h>
#include<algorithm>

struct flower{
    int start;
    int end;
};

int n;
struct flower flowers[100005];
int day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool comp(flower i, flower j){
    if(i.start < j.start) return true;
    return false;
}

int findDateSum(int month, int date){
    int daySum=0;
    for(int i=0 ; i<month ; i++) daySum += day[i];
    return daySum + date;
}

int main()
{
    using namespace std;

    scanf("%d", &n);
    for(int i=0 ; i<n ; i++){
        int a, b, c, d;
        scanf("%d %d %d %d", &a, &b, &c, &d);
        flowers[i].start = findDateSum(a, b);
        flowers[i].end = findDateSum(c, d);
    }

    sort(flowers, flowers+n, comp);
    //for(int i=0 ; i<n ; i++) printf("%d %d\n", flowers[i].start, flowers[i].end);

    int s = 0, e = 60, i=0, max=-1, ans=0; //e_init = 31 + 28 + 1
    while(e <= (findDateSum(11, 30))){
        while(flowers[i].start <= e && i<n){
            if(max < flowers[i].end) max = flowers[i].end;
            i++;
        }

        if(max == -1){
            printf("0");
            return 0;
        }
        
        ans++;
        s = e;
        e = max;
        max = -1;
    }
    printf("%d", ans);
    return 0;
}

 

새로 만든 백준 계정에서 처음으로 푸는 문제라서, 첫 제출부터 '틀렸습니다' 가 나오면 어떡하지 하는 걱정도 있었는데,

다행이었다.

 

예전에도 백준 문제 풀 때마다 느꼈던 건데, 저 '맞았습니다!!' 글씨체가 사람 기분을 굉장히 좋게 해주는 것 같다.