[백준] No.2513 - 통학버스 (C++)
문제
https://www.acmicpc.net/problem/2513
2513번: 통학버스
첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2<=N<=30,000이다. 두 번째 정수 K는 1<=K<=2,000이며, 통학버스의 정원이다. 세
www.acmicpc.net
풀이
solved.ac 난이도: Gold 3
풀이는 간단했지만 구현이 까다로웠던 그리디 문제.
일단 학교는 가장 오른쪽 끝에만 있다고 생각하고 문제를 풀어보자.
만약 가까운 순대로 학생을 최대한 정원만큼 태운다면 어떻게 될까?
아래와 같은 예제를 생각해보자.
버스 정원 : 6
학교로 부터의 거리 | 3(A 아파트) | 2(B 아파트) | 1 | 0 |
학생수 | 4 | 5 | 0 | 학교 |
가까운 학생들을 먼저 태운다면
B아파트에서 5명을 먼저 태우고 남은 한 자리를 위해 A아파트로 이동하여 1명을 더 태운 후 학교로 간다.
그 후 A아파트의 나머지 3명을 태우기 위해 다시 A아파트로 이동후 복귀하면
총 이동 거리는 (2+1+3) + (3+3) = 12이다.
하지만 가장 먼 아파트부터 학생을 최대한 태운다면
A아파트에서 3명을 태운 후 학교로 돌아가는 길에 B아파트에서 남은 자리에 3명을 태우고 복귀한다.
그 후에는 B아파트의 남은 인원만 태우고 복귀하면 된다.
따라서 총 이동거리는 (3+1+2) + (2+2) = 10이다.
즉 먼 곳부터 학생을 태우면 복귀하는 길을 이용하여 남은 자리도 효율적으로 태울 수 있다.
학교로부터 왼쪽과 오른쪽에 아파트들이 있더라도 한쪽에서 다른 한쪽으로 이동할 때는 학교를 지나갈 수밖에 없기 때문에 서로 독립적으로 구현해도 상관이 없다.
구현을 위해 일단 학교의 왼편과 오른편을 나누어 left_v, right_v에 각각 저장해준다.
이때 미리 학교로부터의 거리를 저장해서 담아주자.
1
2
3
4
5
6
7
8
9
10
11
12
|
int pos,num;
for(int i=0; i<apart_num ; ++i){
cin>>pos>>num;
v.push_back(make_pair(pos,num));
}
for(vector<pair<int,int>>::iterator it = v.begin() ; it <v.end() ; ++it){
if(it->first < school_pos )
left_v.push_back(make_pair( abs(school_pos - it->first),it->second));
else
right_v.push_back(make_pair( abs(school_pos - it->first),it->second));
}
|
cs |
그 후 먼 곳부터 정렬되도록 left_v, right_v를 내림차순으로 정렬해준다.
이제 먼 곳부터 방문하면서 정원을 채우는 코드를 구현한다.
1. 남은 자리(left_sit) 보다 해당 위치(apt_idx)에서 태울 학생 수가 적다면
모두 태우고 해당 위치의 학생 수는 0으로, 남은 자리는 태운 수만큼 줄여준다.
그리고 다음 아파트로 넘어가기 위해 ++apt_idx도 잊지 않는다.
2. 남은 자리(left_sit) 보다left_sit 해당 위치(apt_idx)에서 태울 학생 수가 많다면
남은 자리는 모두 태우고 태운만큼 아파트의 학생수를 줄여준다.
물론 남은 자린 0이다.
3. 남은 자리(left_sit)와 해당 위치(apt_idx)에서 태울 학생 수가 같다면
모두 태우고, 남은 자리는 0으로, 다음 아파트로 넘어가기 위해 ++apt_idx
이때 남은 자리가 중요한 이유는 모두 태웠다면 학교로 복귀해야 하기 때문이다.
만약 left_sit ==0이라면 방문한 곳 중 가장 먼 거리(farthest_len)의 두배만큼을 총 거리(len_sum)에 합해준다.
코드
#include <iostream> | |
#include<algorithm> | |
#include<vector> | |
#include<math.h> | |
using namespace std; | |
int apart_num, capacity, school_pos; | |
int CalcShortestRoute(vector<pair<int,int>>& ret_v){ | |
int len_sum=0, left_sit = capacity; | |
int apt_idx = 0,farthest_len =0; | |
while(apt_idx < ret_v.size()){ | |
if(left_sit > 0) | |
farthest_len = max(farthest_len, ret_v[apt_idx].first); | |
if(left_sit > ret_v[apt_idx].second){ | |
left_sit -= ret_v[apt_idx].second; | |
ret_v[apt_idx].second=0; | |
++apt_idx; | |
}else if(left_sit < ret_v[apt_idx].second){ | |
ret_v[apt_idx].second -= left_sit; | |
left_sit=0; | |
} | |
else{ | |
ret_v[apt_idx].second=0; | |
left_sit=0; | |
++apt_idx; | |
} | |
if(left_sit == 0 || apt_idx>=ret_v.size()){ | |
len_sum += 2*farthest_len; | |
farthest_len= 0; | |
left_sit = capacity; | |
} | |
} | |
return len_sum; | |
} | |
int main() { | |
ios_base::sync_with_stdio(0); | |
cin>>apart_num>>capacity>>school_pos; | |
vector<pair<int,int>> v,left_v,right_v; | |
int pos,num; | |
for(int i=0; i<apart_num ; ++i){ | |
cin>>pos>>num; | |
v.push_back(make_pair(pos,num)); | |
} | |
for(vector<pair<int,int>>::iterator it = v.begin() ; it <v.end() ; ++it){ | |
if(it->first < school_pos ) | |
left_v.push_back(make_pair( abs(school_pos - it->first),it->second)); | |
else | |
right_v.push_back(make_pair( abs(school_pos - it->first),it->second)); | |
} | |
sort(left_v.begin(), left_v.end(),greater()); | |
sort(right_v.begin(), right_v.end(),greater()); | |
cout<<CalcShortestRoute(left_v) + CalcShortestRoute(right_v)<<'\n'; | |
return 0; | |
} |