[BaekJoon][2457] 공주님의 정원

BAEKJOON ONLINE JUDGE

2457 공주님의 정원

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

구현 문제

3월 1일부터 11월 30일까지 정원에 꽃이 비지 않으면서 최소한의 꽃을 선택을 하려면 

특정 꽃이 지기 전에 피면서 가장 오래 피어있을 꽃을 선택하여 줄줄이 이어 선택해 나가 12월 1일 이후에 지는 꽃을 마지막으로 선택하면 된다.

꽃을 시작점을 중심으로 정렬하여 지는 날이 가장 긴 꽃을 찾아 선택하여도 되고, 정렬없이 입력 배열을 탐색하면서 꽃을 찾아도 된다.

처음 구현한 코드

#include <stdio.h>
 
typedef struct tagFlower {
    int smon, sday;
    int emon, eday;
    int check;
}Flower;
 
Flower flower[100000];
int n;
 
void input()
{
    int i;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++) {
        scanf("%d %d %d %d", &flower[i].smon, &flower[i].sday, 
                             &flower[i].emon, &flower[i].eday);
    }
}
 
int check(int idx, Flower f)
{
    if (flower[idx].smon < f.emon || 
        (flower[idx].smon == f.emon && flower[idx].sday <= f.eday))
        return 1;
    return 0;
}
 
void process()
{
    int idx;
    int i;
    int flag = 0;
    int cnt = 0;
    Flower f,  temp;
 
    f.emon = 3;
    f.eday = 1;
    for (i = 0; i < n; i++) {
        if (!flower[i].check)    {
            if (flower[i].smon < 3 || (flower[i].smon == 3 && flower[i].sday == 1)) {
                if (flower[i].emon > f.emon 
                    || (flower[i].emon == f.emon && flower[i].eday > f.eday)) {
                    f = flower[i];
                    flower[i].check = 1;
                    flag = 1;
                }
            }
        }
    }
    cnt = flag;
    
    while (f.emon <= 11 && flag) {
        flag = 0;
        temp = f;
        for (i = 0; i < n; i++) {
            if (!flower[i].check && check(i, f)) {
                if (flower[i].emon > temp.emon 
                    || (flower[i].emon == temp.emon && flower[i].eday > temp.eday)) {
                    flag = 1;
                    temp = flower[i];
                }
            }
        }
        if (flag) {
            cnt++;
            f.emon = temp.emon;
            f.eday = temp.eday;
        }
    }
 
    if ((f.smon < 3 || (f.smon == 3 && f.sday == 1)) && f.emon > 11)    printf("%d\n", cnt);
    else printf("0\n");
}
 
int main()
{
    input();
 
    process();
    return 0;
}

이후 수정한 코드

#include <stdio.h>
 
typedef struct tagFlower{
    int start;
    int end;
}Flower;
 
Flower flower[100010];
 
void quicksort(int start, int end)
{
    int left = start;
    int right = end;
    int pivot = flower[(start + end) / 2].start;
    Flower temp;
 
    while (left <= right) {
        while (flower[left].start < pivot) { left++; }
        while (flower[right].start > pivot) { right--; }
 
        if (left <= right) {
            temp = flower[left];
            flower[left] = flower[right];
            flower[right] = temp;
 
            left++;
            right--;
        }
    }
 
    if (left < end) { quicksort(left, end); }
    if (right > start) { quicksort(start, right); }
}
 
int main()
{
    int n;
    int i, j;
    int sm, sd, em, ed;
    int start, end;
    int theend = 1201;
    int index = 0, count = 0, flag = 0;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++) {
        scanf("%d %d %d %d", &sm, &sd, &em, &ed);
        flower[i].start = sm * 100 + sd;
        flower[i].end = em * 100 + ed;
    }
 
    quicksort(0, n - 1);
 
    start = end = 301;
 
    while (start < theend) {
 
        for (i = index; i < n; i++) {
            if (flower[i].start <= start) {
                if (flower[i].end > end) {
                    end = flower[i].end;
                    index = i;
                }
            }
        }
 
        if (start == end) {
            flag = 1;
            start = theend;
        }
        else {
            start = end;
            count++;
        }
    }
 
    if (flag == 1)        printf("0\n");
    else                    printf("%d\n", count);
 
    return 0;
}