[백준 1931번] 회의실 배정 (C++ / python 해보기)

짱구를 굴렸을 때, 음.. 뭔가 그리디하게 선택해서 풀면 되겠다 라고 생각은 했지만,

 

그리디 증명은 어떻게 하지 ?

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
vector<pair<int,int>> v;
bool compare(pair<int,int>& a, pair<int,int>& b){
    if(a.second == b.second)
    {
        return a.first < b.first;
    }else{
        return a.second < b.second;
    }
    
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, cnt =0, la=0;
    cin >> N;
    for(int i = 0; i< N; i++)
    {
        int s,e; // start , end, difference
        cin >> s >> e;
        v.push_back({s,e});
    }
    sort(v.begin(), v.end(), compare);
    for(int i = 0 ; i< N; i++)
    {
        if(la <= v[i].first)
        {
            cnt ++;
            la = v[i].second;
        }
    }
    cout << cnt << endl;
}

---

Python 풀이 ( 이중정렬 해보기 )

import sys
input = sys.stdin.readline

N = int(input().rstrip())

meet = [list(map(int,input().split())) for _ in range(N)]
meet.sort(key= lambda x : (x[1],x[0]))
last = 0
cnt = 0
for time in meet:
    s,e = time[0], time[1]
    if last <= s:
        last = e
        cnt+=1

print(cnt) 

sort에 key값을 넘겨주면 조건에 따라서 정렬할 수 있다.

여기에선 lambda를 썼지만, 함수를 넘겨줄 수도 있음.

내림차순으로 하고싶으면 -x[1]식으로 할 수 있다.