[백준 10165번] [그리디] 버스 노선

사실 이 문제를 잘못 독해해서 시간이 엄청 걸렸다.. 문제에서 다른 노선에 포함 되어있는 것을 지운다고 하였는데, 이 의미를 잘못 이해하였다. 

 

접근 방법은 다음과 같다.

1. 제일 긴 노선을 찾는다.

2. 제일 긴 노선의 출발점을 원점으로 변경한다. (기준점 설정)

3. 출발이 빠른 순으로 정렬한다.

4. 노선들을 순차적으로 방문하되, 이전 도착점보다 도착점이 더 먼 경우에만 해당 노선을 남겨둔다.
(그렇지 않으면 이전 노선에 포함된다는 의미이므로 지워도 무방하다.)

추가적으로 원형 노선에 대해서 살펴볼 필요성이 존재한다.

원형 노선의 경우, 강제로 직선 노선으로 변경해주면 된다.

 

예를 들어 N이 10이고 (5, 2)의 경우에는 강제로 (5, 12)로 만들어주면 직선 노선화시킬 수 있다.

이 문제에서는 2번 과정을 거치고 직선 노선으로 펴주면 된다.

 

원형 노선을 직선 노선으로 변환하는 작업에 대해서 잘 정리해두도록 하자.

 

코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
int max_start; // 가장 긴 것의 시작
int max_end; //  가징 긴 것의 종료
int max_length = -1; // 가장 긴 것의 길이

struct bus{
    int start;
    int end;
    int index_num;
    bus(int temp1, int temp2, int temp3);
};

bus::bus(int temp1, int temp2, int temp3){
    start = temp1;
    end = temp2;
    index_num = temp3 + 1;
}

// Bus vector를 시작시작이 제일 빠르게끔 세팅
bool compare(const bus &data1, const bus &data2){
    if(data1.start == data2.start){
        if(data1.start > data1.end && data2.start < data2.end){
            return true;
        }
        else if(data1.start < data1.end && data2.start > data2.end){
            return false;
        }
        else return data1.end > data2.end; // 시작 지점이 같으면 끝지점이 더 뒤인거를 먼저 체크해서 지워지게끔
    }
    else{
        return data1.start < data2.start; // 기본적으로는 시작지점이 빠른 것이 앞에 오게끔
    }
}

int length_check(int start, int end){
    if(end < start) return N - (start - end);
    return end - start;
}

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> N >> M;
    vector<bus> data_store;

    for(int i = 0; i < M; i++){
        int temp1, temp2;
        cin >> temp1 >> temp2;
        if(length_check(temp1, temp2) > max_length){
            max_length = length_check(temp1, temp2);
            max_start = temp1;
            max_end = temp2;
        }
        data_store.push_back(bus(temp1, temp2, i));
    }// 데이터 저장

    for(int i = 0; i < M; i++){
        data_store[i].start = (data_store[i].start + (N - max_start)) % N;
        data_store[i].end = (data_store[i].end + (N - max_start)) % N;
    } // 좌표 보정

    sort(data_store.begin(), data_store.end(), compare); // 시작시간이 제일 빠르게끔 세팅
    vector<int> result_store; // 생존자 모임
    result_store.push_back(data_store[0].index_num);
    int back_store = data_store[0].end;

    for(int i = 1; i < M; i++){
        int compare_num; // 끝 지점 비교기준
        if(data_store[i].end < data_store[i].start){
            compare_num = data_store[i].end + N;
        }
        else compare_num = data_store[i].end;


        if(compare_num > back_store){
            result_store.push_back(data_store[i].index_num);
            back_store = compare_num;
        }
    }

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

    for(int i = 0; i < result_store.size(); i++){
        cout << result_store[i] << " ";
    }
    cout << "\n";

    return 0;
}