정올 1828 냉장고

정올 문제풀이

1828 : 냉장고

 

 

문제

N개의 화학 물질 C1, C2, …, Cn이 있다.

이들 각각은 보관되어야 할 온도가 각기 다른데, 각 Ci마다 최저 보관 온도 xi와 최고 보관 온도 yi가 정해져 있다. 

즉 Ci는 온도 xi이상, yi이하의 온도에서 보관되어야만 안전하다.

이 화학 물질들을 모두 보관하기 위해서는 여러 대의 냉장고가 필요한데 가능하면 적은 수의 냉장고를 사용하고 싶다. 

이를 해결하는 프로그램을 작성하시오.

 

 

입력형식

첫줄에 화학물질의 수 N이 입력된다. N의 범위는 1이상 100 이하이다.

두 번째 줄부터 N+1줄까지 최저보관온도와 최고보관온도가 입력된다. 

보관온도는 -270° ~ 10000°이며, 각 냉장고는 임의의 정해진 온도를 일정하게 유지할 수 있고, 냉장고는 아주 크다고 가정한다.

 

 

출력형식

첫줄에 최소로 필요한 냉장고의 대수를 출력한다.

 

 

입력 예	출력 예
4 -15 5 -10 36 10 73 27 44	2

 

 

간단 구현설명

최고온도 기준 오름차순 정렬

첫번째 최고온도 저장

냉장고개수 = 1

배열순회 1 ~ n - 1

저장된 최고온도 < arr[i].최저온도 이면

++냉장고개수 and 최고온도 갱신

 

 

 

c 제출코드

#include <stdio.h>
 
typedef struct Data
{
    int xi;
    int yi;
} DATA;
 
DATA dts[100];
 
void QSort(int start, int end)
{
    int l, r;
    DATA pivot, tmp;
 
    if (start >= end)
        return;
 
    pivot = dts[start];
    l = start + 1;
    r = end;
 
    while (l <= r)
    {
        while (l <= r && dts[l].yi < pivot.yi) { ++l; }
        while (l <= r && dts[r].yi >= pivot.yi) { --r; }
 
        if (l < r)
        {
            tmp = dts[l];
            dts[l] = dts[r];
            dts[r] = tmp;
        }
    }
 
    dts[start] = dts[r];
    dts[r] = pivot;
 
    QSort(start, r - 1);
    QSort(r + 1, end);
}
 
int main()
{
    int n, temp, i, resCnt;
 
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d %d", &dts[i].xi, &dts[i].yi);
 
    QSort(0, n - 1);
     
    temp = dts[0].yi;
    resCnt = 1;
    for (i = 1; i < n; i++)
    {
        if (temp < dts[i].xi)
        {
            ++resCnt;
            temp = dts[i].yi;
        }
    }
 
    printf("%d", resCnt);
 
    return 0;
}

 

c++ 제출코드

#include <iostream>
#include <algorithm>
 
struct Data
{
    int yi;
    int xi;
};
 
bool compare(Data dt1, Data dt2)
{
    return dt1.yi < dt2.yi;
}
 
int main()
{
    int n;
    Data dts[100];
 
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &dts[i].xi, &dts[i].yi);
 
    std::sort(dts, dts + n, compare);
 
    int resCnt = 1;
    int temp = dts[0].yi;
    for (int i = 1; i < n; i++)
    {
        if (temp < dts[i].xi)
        {
            ++resCnt;
            temp = dts[i].yi;
        }
    }
 
    printf("%d", resCnt);
 
    return 0;
}