백준 14469번 - 소가 길을 건너간 이유 3 (C++)

유형: 그리디

문제: https://www.acmicpc.net/problem/14469

14469번: 소가 길을 건너간 이유 3

 

풀이

입력을 받아와 pair 형식으로 벡터에 저장하고, 시작 시간이 낮은 순으로 정렬한다.

만약 시작 시간이 같다면 소요 시간이 낮은 순으로 정렬한다.

이런 조건대로 정렬한 뒤, 벡터 원소를 순회하면서 조건에 따라 시간을 더하면 된다.

 

현재 시간을 cnt라고 할 때, cnt가 원소 시작 시간보다 작다면, cnt를 시작 시간으로 갱신한다.

이는 다음 소가 도착할 시간까지 대기하는 것을 의미한다.

이후 소요시간을 cnt에 더해주면 된다.

 

c++에서 sort 함수 커스텀을 연습하기 좋은 문제.

정렬 조건을 bool 함수에 적은 뒤, sort 함수에서 세번째 인자로 이름만 넘겨주면 된다.

참고로 기본은 오름차순, greater<>()을 쓰면 내림차순이다.

 

#include "iostream"
#include "algorithm"
#include "vector"

using namespace std;

bool cmp(pair<int, int> x, pair<int, int> y){
    // 첫번째 원소가 같다면, 두번째 원소가 더 작은 것이 먼저 옵니다.
    if(x.first == y.first) return x.second < y.second;
    else return x.first < y.first; // 그 외엔 첫번째 원소가 더 작은게 먼저
}

int main(){
    int n; cin >> n;
    int cnt = 0;
    vector<pair<int,int>> arr;

    while(n--){
        int start, term; cin >> start >> term;
        pair<int, int> temp(start,term);
        //temp = make_pair(start,term); // 동일
        arr.push_back(temp);
    }

    // 비교함수 기준으로 정렬
    sort(arr.begin(), arr.end(), cmp);

    for(auto now: arr){
        // 현재 시간이 first보다 작다면 first로 갱신
        if(cnt < now.first) cnt = now.first;
        // 소요시간인 second를 더해준다
        cnt += now.second;
    }

    cout << cnt;
    return 0;
}