1일차 (월) : 24229번, 모두싸인 출근길 (G4)

문제 : 그리디 알고리즘을 활용하여 선형으로 문제를 해결할 수 있다. 문제 정의를 잘 한다면 어렵지 않게 구현 가능하다.

풀이과정

1. 판자를 시점을 기준으로 오름차순으로 정렬한다. 이는 판자를 연결하기 위함이다.
2. 반복문을 판자의 수(n) 번 실행하며 문제를 선형으로 해결할 수 있다.
3. 판자를 합칠 수 있다면 합친다. (ep 갱신)
4. 합칠 수 없지만, 뛰어서 넘어갈 수 있다면 넘어간다. (sp와 ep 갱신)
5. 매 반복마다 mp를 갱신하며 뛰어 넘어갈 수 있는 최대값을 구한다.
6. n번 반복 후 ep를 출력한다.
7. 정답

풀이 코드

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define fastio                    \\
    ios_base::sync_with_stdio(0); \\
    cin.tie(0);                   \\
    cout.tie(0)

int main()
{
    fastio;

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

    int sp = path[0].first, ep = path[0].second;
    int mp = ep + ep - sp;

    for (int i = 1; i < n; i++) {
            if (path[i].first <= ep)
                ep = max(ep, path[i].second);
            else if (path[i].first <= mp) {
                sp = path[i].first;
                ep = path[i].second;
            }
            mp = max(mp, ep + ep - sp);
        }
    cout << ep;

    return 0;
}

반례