아이디어

예제 분석

우선 예제의 데이터를 분류할 수 있는 가장 큰 기준은 누가봐도 순행과 역행일 것이다.

즉, 순행하는 데이터와 역행하는 데이터로 나눈 다음에 생각해 보자.

순행

우선 순행하는 데이터의 경우 어쨌든 상근이는 M번에 위치하는 집에 가야하기 때문에 가는 도중에 내려주면 되므로 신경쓰지 않아도 된다.
(도착지가 출발지보다 크고, 배의 정원에는 제한이 없기 때문에)

역행

반면에 역행하는 데이터의 경우에는 역행하는 만큼의 이동을 두 번 더 해야 된다.
(도착지까지 갔다가, 출발지까지 다시 와야 됨)

하지만 이때 행선직가 겹치는 손님의 경우 같이 태우면 이동거리가 줄어들게 된다.

이렇게 한 분석을 통해서 코드로 한번 구현해 보자

해법

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

long long min_distance(vector<pair<int, int>>& customer_need, long long customer_num, long long house_num);

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    long long customer_num, house_num;
    cin >> customer_num >> house_num;
    vector<pair<int, int>> customer_need;
    for (int i = 0; i < customer_num; i++) {
        int x, y;
        cin >> x >> y;
        customer_need.push_back({ x, y });
    }

    cout << min_distance(customer_need, customer_num, house_num);

    return 0;
}

long long min_distance(vector<pair<int, int>>& customer_need, long long customer_num, long long house_num) {
    long long distance = house_num;
    vector<pair<int, int>> v1, v2;
    for (int i = 0; i < customer_num; i++) {
        if (customer_need[i].first > customer_need[i].second)
            v1.push_back({customer_need[i].second, customer_need[i].first});
    }// 역행하는 손님들만 고려하면 됨

    if (v1.empty())
        return distance;

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

    v2.push_back(v1[0]);
    for (int i = 1; i < v1.size(); i++) {
        if (v2.back().second >= v1[i].first)
            v2.back().second = max(v1[i].second, v2.back().second);
        else
            v2.push_back(v1[i]);
    }
    // 역행하는 손님중 겹치는 부분이 있을 때, 출발지는 최대값, 도착지는 최소값으로 정함.

    for (int i = 0; i < v2.size(); i++) {
        distance = distance + 2 * (v2[i].second - v2[i].first);
    }
    // 거리계산

    return distance;
}

주의점

1) pair 순서

pair<int, int>(first, second)

이 경우는 출발지(도착지보다 큰 값)를 앞에, 도착지를 뒤에, 즉 원래 데이터 그대로 넣는 방식이다.

pair<int, int>(second, first)

이 경우는 도착지(출발지 보다 작은 값)를 앞에, 출발지를 뒤에 넣는 방식이다.

위처럼 pair를 구성하는 방법에는 두가지가 있을 것이다.

처음에 이 코드를 구현할 때에는 첫번째를 활용하여 구현하였었다. 하지만 이 때 예제 코드에서는 잘 돌아갔지만, 백준 채점에서는 틀린 것으로 나왔다.

그 이유를 생각해 보면, pair를 vector에 넣은 후 sort부분에서 도착지를 기준으로 정렬하기 때문에, 정렬이 제대로 되지 않았을 것이라고 추측해 본다.

2) 맨 처음 짠 코드

아래는 맨 처음 짠 코드이다.
보시다 싶이 코드를 더 간결하게 줄일 수 있음에도 살짝 복잡한 것을 볼 수 있다.

가장 큰 문제는 sort를 맨 나중에 해서 문제 해결을 파악하는데 더 복잡했을 것이다.

inline int min_distance(vector<pair<int, int>>& customer_need, int customer_num, int house_num) {
    int distance = house_num;
    vector<pair<int, int>> v1;
    for (int i = 0; i < customer_num; i++) {
        if (customer_need[i].first > customer_need[i].second)
            v1.push_back(pair<int, int>(customer_need[i].first, customer_need[i].second));
    }// 역행하는 손님들만 고려하면 됨

    for (int i = 0; i < v1.size() - 1; i++) {
        for (int j = i + 1; j < v1.size(); j++) {
            if (v1[i].first >= v1[j].second && v1[i].second <= v1[j].first) {
                v1.push_back(pair<int, int>(max(v1[i].first, v1[j].first), min(v1[i].second, v1[j].second)));
                if (i < j) {
                    v1.erase(v1.begin() + j);
                    v1.erase(v1.begin() + i);
                }
                else {
                    v1.erase(v1.begin() + i);
                    v1.erase(v1.begin() + j);
                }
                j--;
            }
        }
    }// 역행하는 손님중 겹치는 부분이 있을 때, 출발지는 최대값, 도착지는 최소값으로 정함.

    sort(v1.begin(), v1.end());
    // 정렬, 이때 위의 작업으로 경로가 겹치는 손님은 없을 것임

    for (int i = 0; i < v1.size(); i++) {
        distance = distance + 2 * (v1[i].first - v1[i].second);
    }
    // 거리계산

    return distance;
}

3) 메모리 초과

이 코드는 생각한 해법을 그대로 구현한 코드이다.

때문에 이해하기 쉽고, 구현하기 간단하여 적은수의 데이터에서는 활용할 수 있지만, house num이 많아질 경우, 저장공간이 매우 커져 메모리 초과를 일으켰다.
(백준 기준)

int min_distance(vector<pair<int, int>>& customer_need, int customer_num, int house_num) {
    int distance = house_num;
    vector<pair<int, int>> v1;
    for (int i = 0; i < customer_num; i++) {
        if (customer_need[i].first > customer_need[i].second)
            v1.push_back(pair<int, int>(customer_need[i].first, customer_need[i].second));
    }// 역행하는 손님들만 고려하면 됨

    int* check = new int[house_num+1];
    for (int i = 0; i < house_num+1; i++)
        check[i] = 0;
    for (int i = 0; i < v1.size(); i++) {
        for (int j = v1[i].second; j <= v1[i].first; j++)
            check[j] = 1;
    }
    int num = 0;
    for (int i = 0; i < house_num; i++) {
        if (check[i] == 1 && check[i + 1] == 1)
            num++;
    }
    cout << num << endl;
     // 역행하는 손님중 겹치는 부분이 있을 때, 출발지는 최대값, 도착지는 최소값으로 정함.

    distance = distance + 2 * num;
    // 거리계산

    delete[] check;
    return distance;
}// 메모리 초과