[정올] 냉장고

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=3050 

JUNGOL

그리디 알고리즘을 사용하는 문제입니다. 

 

문제부터 간단하게 요약하면, 화학 물질들은 각각 보관 온도 범위를 가집니다. 이 때, 냉장고들은 각각 하나의 온도만을 유지할 수 있습니다. 이 때, 화학 물질들을 모두 보관하기 위한 냉장고의 최소 갯수를 구해야 합니다. 

 

<Solution>

그리디 알고리즘을 사용해야 합니다. 

 

그리디 알고리즘도 정렬을 해야 합니다. y 즉 화학물질 보관의 최대 온도 기준으로 정렬을 시킵니다. 

 

그리고 간단한 예시를 봅시다. 

4
-15 5
-10 36
10 73
27 44

정렬을 시키면 위와 같은 상황이 됩니다. 

왜 뒤의 온도로 정렬하면 그리디한 알고리즘이 가능한지 위의 그림을 보면 됩니다. 처음 냉장고의 온도를 5도로 잡으면, 이후로 시작 온도가 5 이하인 애들은 모두 없애주어도 됩니다. 

 

다음으로 시작온도를 44도로 잡으면 이후의 것들을 모두 없애줄 수 있습니다. 이 로직으로 구현을 하면 됩니다.

 

실제 코드는 아래와 같습니다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int X[100+10];
int Y[100+10];
 
struct chemical {
    int x, y;
}chemicals[100+10];
 
 
 
void InputData(){
    cin >> N;
    for (int i=0; i<N; i++){
        // cin >> X[i] >> Y[i];
        cin >> chemicals[i].x >> chemicals[i].y;
    }
}
bool compare(struct chemical a, struct chemical b){
    return a.y < b.y;
}
int solution(){
    // sort by y
    sort(chemicals, chemicals+N, compare);
    int cur_y = chemicals[0].y;
    int cnt = 1;
    for(int i = 1; i<N; i++){
        if(chemicals[i].x <= cur_y) continue;
        cur_y = chemicals[i].y;
        cnt++;
 
    }
    return cnt;
 
 
 
}
 
int main(){
    int ans = -1;
 
    InputData();// 입력받는 부분
 
    // 여기서부터 작성
    ans = solution();
 
    cout << ans << endl;// 출력하는 부분
    return 0;
}