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

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

2513번: 통학버스

 

 

수용 한계량이 있는 통학버스가 존재할 때, 모든 학생을 태울 수 있는 최소거리를 찾는 문제입니다.
생각을 해보면 모든 학생을 태워야 하므로 멀리 있는 학생 위치도 결국엔 한 번 이상은 지나야 합니다. 그래서 멀리 있는 학생들부터 태워서 오는 길에 수용량이 남으면 태우는 방법으로 하면 최소거리를 구할 수 있는 그리디 문제입니다.

 

통학버스의 시작 위치를 s라 하면 s의 왼쪽에 존재하는 학생과 오른쪽에 존재하는 학생들을 서로 다른 vector에 집어넣고 멀리 있는 학생들부터 처리할 수 있도록 sort를 해줍니다. 그리고 while loop을 돌면서 해당 vector가 빈 vector가 되도록 로직을 실행하게 하면 쉽게 구현 가능한 문제입니다.

 

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

using namespace std;


int caculateDistance(vector<pair<int, int>> & Students, int k, int s){
    int nowPos, nowNum, ans;

    nowPos = s;
    nowNum = 0;
    ans = 0;
    
    while(!Students.empty()){
        int pos = Students.back().first;
        int num = Students.back().second;
        
        if(num + nowNum <= k){
            Students.pop_back();
            nowNum += num;
        }
        else{
            Students.back().second -= k - nowNum;
            nowNum += k - nowNum;
        }

        ans += abs(nowPos - pos);
        nowPos = pos;

        if(nowNum == k || Students.empty()){
            ans += abs(nowPos - s);
            nowPos = s;
            nowNum = 0;
        }
    }

    return ans;
}

int main(){

    int n, k, s;
    cin >> n >> k >> s;
    
    vector<pair<int, int>> leftStudents, rightStudents;

    for(int i=0; i<n; i++){
        int pos, num;
        cin >> pos >> num;
        if(pos < s){
            leftStudents.push_back(make_pair(pos, num));
        }
        else if(pos > s){
            rightStudents.push_back(make_pair(pos, num));
        }
    }

    sort(leftStudents.begin(), leftStudents.end(), greater<>());
    sort(rightStudents.begin(), rightStudents.end(), less<>());

    cout << caculateDistance(leftStudents, k, s) + caculateDistance(rightStudents, k , s);

    return 0;
}