[C++] 백준 2513 - 통학버스

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

2513번: 통학버스

<풀이>

1. 학생이 사는 아파트의 범위를 저장한다.(학생이 사는 아파트 중 가장 작은 index, 가장 큰 index를 저장한다.)

2. 아파트 중 가장 작은 index에서 시작해서 학교까지 버스에 태울 수 있을 만큼 모두 태운다.

3. 학교보다 왼쪽에 있는 학생들을 모두 태울 때 까지 반복하고, 거리를 저장한다.

4. 학교보다 오른쪽에 사는 학생도 2,3번을 반복한다.

#include <iostream>
using namespace std;
 
int N, K, S;
int arr[100000];
int aptStr = -1, aptEnd = 0;
int res = 0;
 
int main() {
 
    //입력
    cin >> N >> K >> S;
    for (int i = 0; i < N; i++) {
        int index, num;
        cin >> index >> num;
        arr[index] = num;
 
        //학생이 사는 아파트 중 처음과 끝 아파트 찾기 
        if (aptStr == -1 || index < aptStr) {
            aptStr = index;
        }
        if (index > aptEnd) {
            aptEnd = index;
        }
    }
 
    //처음 아파트 부터 학교까지 버스 이동거리 구하기
    while (aptStr < S) {
        //str : 학생을 태우기 시작한 아파트, end : 여기 학생까지 태운 아파트, tmpK : 버스에 남은 자리
        int str = aptStr, end = aptStr, tmpK = K;
 
        if (arr[str] > 0) {
            while (true) {            
                if (tmpK == 0 || end == S) {
                    aptStr = end;
                    res += (S - str) * 2;
                    break;
                }
 
                if (arr[end] > tmpK) {
                    arr[end] -= tmpK;
                    tmpK = 0;
                }
                else {
                    tmpK -= arr[end];
                    arr[end] = 0;
                    end++;
                }
                
            }
        }
        else {
            aptStr++;
        }
    }
 
    //끝 아파트 부터 학교까지 버스 이동거리 구하기
    while (aptEnd > S) {
        int str = aptEnd, end = aptEnd, tmpK = K;
 
        if (arr[str] > 0) {
            while (true) {
                if (tmpK == 0 || end == S) {
                    aptStr = end;
                    res += (str - S) * 2;
                    break;
                }
                if (arr[end] > tmpK) {
                    arr[end] -= tmpK;
                    tmpK = 0;
                }
                else {
                    tmpK -= arr[end];
                    arr[end] = 0;
                    end--;
                }
            }
        }
        else {
            aptEnd--;
        }
    }
    cout << res;
 
    //예제 테스트 케이스
    /*7 4 4
        0 5
        1 2
        2 3
        6 4
        7 6
        8 6
        9 7*/
    //output : 66
}

 

구현에 대해 알아볼 수 있는 문제였습니다.