14469: 소가 길을 건너간 이유 3 - 그리디

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

문제요약

도착한 시간과, 검문 시간이 주어질 때 모든 소가 출입하는데 걸리는 최소 시간.

 

난이도

Silver 4

---

풀이 포인트

• max
• 그리디

---

REVIEW

바로 맞아버려서 의아했다.

하지만 모범 풀이에서 다음 소가 도착한 시간과, 이전 소가 점검을 마친 시간 사이에 간극이 있을 때,

시간을 갱신해주는 로직과, 시간 경과를 더해주는 과정이 훨씬 간결하다. 배워두기.

 

또 따로 int형에 숫자를 받아 pair에 넣는 방식이 아니라 바로 pair요소에 집어넣는 것도 훨씬 간결해보인다.

 

---

CODE

// Mine

#include <bits/stdc++.h>
using namespace std;
int t,a,b;
vector<pair<int, int>> v;
int crtT;

int main(){
    cin >> t;

    for(int i = 0; i < t; i++){
        cin >> a >> b;
        v.push_back({a,b});
    }

    sort(v.begin(), v.end());

    crtT = v[0].first;

    for(pair<int, int> p : v){
        if(crtT < p.first){
            crtT = p.first;
        }

        for(int i = 0 ; i < p.second; i++){
            crtT++;
        }
    }

    cout << crtT;
    
}

// 모범

#include <bits/stdc++.h>
using namespace std;

int n;

int main(){
    cin >> n;
    vector<pair<int, int>> a(n);

    for(int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
    sort(a.begin(), a.end());

    int realTime = a[0].first + a[0].second;

    for(int i =1; i < a.size(); i++){
        realTime = max(realTime, a[i].first);
        realTime += a[i].second;
    }

    cout << realTime << '\n';

}