[백준] No.2513 - 통학버스 (C++)

문제

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

2513번: 통학버스

 

풀이

 

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에 각각 저장해준다.

이때 미리 학교로부터의 거리를 저장해서 담아주자.

 

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));
}

 

그 후 먼 곳부터 정렬되도록 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)에 합해준다.

 

 

코드