BOJ 2513 - 통학버스

www.acmicpc.net/problem/2513

2513번: 통학버스

 

이 문제는 도서관 (sdy-study.tistory.com/169) 문제와 접근 방법이 유사하다

학교를 기준으로 좌측 부분 탐색하고, 우측 부분 탐색하면서,

학생들을 버스에 승차시키고 승차시키지 못한 학생들은 다시 방문하러 가는 방식으로 처리한다

 

다만, 다시 방문하는 지역을 최대한 학교와 가까운 지역으로 선정해야한다.

그래서, 좌측 방문시에는 왼쪽 맨 끝 아파트에서 부터 승차를 시켜야하고, 

마찬가지 논리로 우측 방문시에는 오른쪽 맨 끝 아파트에서 부터 승차를 시켜야한다.

 

제일 먼 곳에 있는 학생들을 먼저 승차시킴으로써, 버스의 이동 거리를 최소화하는 그리디 문제였다.

 

(그리디이긴 하지만, 사실상 구현이 더 관건인것 같다)

 

 

- C++

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int N, K, S, answer; // 아파트 단지 수, 통학버스 정원, 학교위치 
vector<pair<int, int>> apartment; // 위치, 학생 수 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> K >> S;
    
    for(int i = 0; i < N; ++i) {
        int pos, num;
        cin >> pos >> num;
        apartment.push_back({pos, num});
    }
    apartment.push_back({S, 0});
    
    sort(apartment.begin(), apartment.end());
    
    int idx = -1; // 학교의 좌표 
    for (int i = 0; i < apartment.size(); ++i)
        if (apartment[i].first == S)
            idx = i;
        
    // 좌측 탐색    
    for (int i = 0; i < idx; ) {
        int num = 0, j;
        for (j = i; j < idx; ++j) { // 못타는 학생도 있을수 있으므로 이중포문 
            num += apartment[j].second;
            if (num > K) { // 학교버스 수용인원 초과시 
                apartment[j].second = num - K;
                break;
            }
        } 
        answer += (S - apartment[i].first) * 2; // 거리 계산 
        i = j;
    }
    
    // 우측 탐색
    for (int i = apartment.size() - 1; i > idx; --i) {
        int num = 0, j;
        for (j = i; j > idx; --j) {
            num += apartment[j].second;
            if (num > K) {
                apartment[j].second = num - K;
                j++;
                break;
            }
        }
        answer += (apartment[i].first - S) * 2;
        i = j;
    } 
    
    cout << answer;
    
    return 0;
}