[백준 2513번] 통학버스 (C++)

문제링크 : https://www.acmicpc.net/problem/2513

2513번: 통학버스

 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N, K, S;  //단지 수, 통학버스 정원, 학교 위치

vector<pii> lefts;
vector<pii> rights;

int distance(vector<pii> v)
{
    int pos = S, num = 0, result = 0;
    
    while(!v.empty())
    {
        auto [npos, nnum] = v.back();
        if(num + nnum <= K) //정원미만이면
        {
            v.pop_back();
            num += nnum; //인원수 담기
        }
        else  
        {
            v.back().second -= (K - num); //수용가능 인원 체크
            num += (K-num);  //수용가능한 인원만 담기
        }

        result += abs(pos - npos);  //현재 담은 인원까지 거리 저장
        pos = npos; //현재 위치 저장

        if(num == K)  //정원이 찼다면
        {
            result += abs(pos - S);
            pos = S;
            num = 0;
        }
    }
    result += abs(pos - S);

    return result;
}

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

    cin >> N >> K >> S;

    for(int i=0; i<N; i++)
    {
        int pos, num;
        cin >> pos >> num;  //위치, 학생 수
        if(pos < S) lefts.push_back({pos, num});  //학교보다 왼쪽
        else rights.push_back({pos, num});  //학교보다 오른쪽
    }
    
    //멀리있는 학생부터 태우도록 정렬
    sort(lefts.begin(), lefts.end(), greater<>());  
    sort(rights.begin(), rights.end());

    cout << distance(lefts) + distance(rights);

    return 0;

}

학교를 기준으로 왼쪽과 오른쪽을 확인해야 하므로 각각에 대한 벡터를 선언한다.

해당 벡터에 페어로 위치와 학생수를 넣고 멀리 있는 사람부터 태우도록 정렬을 해준다. 

주의해야할 것이 back()으로 접근하므로 정렬은 버스기준으로 가깝게 정렬해줘야 한다.

 

멀리 있는 곳부터 인원을 태우기 시작하고, 한번 태울때 마다 현재까지의 거리와 위치를 넘겨준다.

만약 도착한 곳의 인원이 정원을 초과하면 수용가능한 인원을 체크하여 수용가능한 인원만 태운다.

 

이렇게 정원이 차게된다면 학교까지 돌아와야므로 학교까지의 거리를 담고 현재 위치와 인원을 초기화한다.

인원이 남았다면 (== 벡터에 남은 값이 있다면) 다시 탐사를 시작하고 모두 태워서 더 이상 탐사할 값이 없다면 다시 학교로 돌아오며 마찬가지로 현재 위치부터 학교까지의 거리를 저장한다.