문제

주택난을 해결하기 위해서 직선 도로 하나를 따라 여러 아파트 단지들을 지었다. 또, 이 아파트 단지 주민을 위해 도로 위 한 지점에 학교 하나를 신설하였다. 아파트 단지들이 서로 멀리 떨어져 있기 때문에 반드시 통학버스를 이용해서만 다닐 수 있고, 통학버스는 한 대이다.

각각의 아파트 단지와 학교의 위치는 도로 위의 좌표로 주어지며, 또 각 아파트 단지마다 여기에 사는 학생들의 수도 주어진다. 통학버스는 아침에 학교를 출발하여 각 아파트 단지에 있는 학생들을 태우고 학교로 다시 돌아온다. 이 통학버스는 정원을 초과하여 학생을 태울 수 없고, 모든 학생을 등교시킬 때까지 이 과정을 반복한다.

위 규칙을 따라서 모든 학생들을 학교에 등교시키는 예를 보자. 아파트 단지 A, B, C가 각각 좌표 0, 2, 5에 있고 이 단지에 사는 학생은 각각 1, 2, 1명이라고 하자. 두 지점 간의 거리는 두 지점 좌표의 차이로 정의된다. 최대 4명이 탈 수 있는 통학버스가 좌표 4에 있는 학교에서 출발해서 모든 학생들을 등교시킬 때, 버스는 먼저 단지 B를 들러 2명을 태우고, 단지 A를 들러서 1명을 태우고 다시 학교로 돌아온다면 이동 거리는 2 + 2 + 4 = 8이다. 다시 학교에서 아파트 단지 C로 이동하여 1명을 태우고 돌아오면 이동 거리는 1 + 1 = 2가 되고, 총 이동거리는 8 + 2 = 10이 된다.

학교의 위치, 각각의 아파트 단지의 위치와 학생 수, 통학버스의 정원이 주어졌을 때, 모든 학생을 등교시키는데 필요한 통학버스의 총 이동 거리의 최솟값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2 ≤ N ≤ 30,000이다. 두 번째 정수 K는 1 ≤ K ≤ 2,000이며, 통학버스의 정원이다. 세 번째 정수 S는 학교의 위치를 나타낸다. 둘째 줄부터 N+1번째 줄에는 각 아파트 단지의 위치를 나타내는 정수와 이 단지에 사는 학생 수를 나타내는 정수가 빈칸을 사이에 두고 주어진다. 학교와 아파트 단지의 좌표는 0 이상 100,000 이하이며, 이 좌표들은 모두 서로 다르다. 각 아파트 단지의 학생 수는 1 이상 2,000 이하이다.

출력

첫째 줄에 주어진 입력에서 통학버스의 최소 이동 거리를 출력한다. 최소 이동 거리가 1,000,000,000을 초과하는 경우는 없다.

입출력 예

입력

풀이

그리디 알고리즘 문제
1. 위치 기준으로 아파트 단지를 정렬
2. 학교 기준 왼쪽 단지의 학생을 모두 등교시키는 거리 구함
3. 학교 기준 오른쪽 단지의 학생을 모두 등교시키는 거리 구함

코드

package _0419;
import java.io.*;
import java.util.*;
public class Main_B2513 {
	//단지의 위치와 학생 수를 저장할 클래스
	static class Point implements Comparable<Point>{
		int pos,cnt;
		Point(int pos,int cnt){
			this.pos=pos;
			this.cnt=cnt;
		}
		//위치 기준 오름차순 정렬
		@Override
		public int compareTo(Point o) {
			return this.pos-o.pos;
		}
	}
	//입력값 버스 정원, 학교 위치
	static int K,S;
	//아파트 단지 저장 배열
	static Point[]arr;
	//탐색 메서드(시작지점, 탐색해야 되는 단지 수, 탐색이 왼쪽이면 true/오른쪽이면 false)
	static int search(int start,int target,boolean left) {
		//남은 좌석, 현재 위치, 거리 합, 현재 단지까지의 거리, 학생을 등교시킨 단지 수
		int seat=K,cur=start,ans=0,dist=0,finish=0;
		//탐색해야할 단지를 모두 탐색할 때까지
		while(finish<target) {
			//남은 좌석이 없는 경우
			if(seat==0) {
				//학교 왕복 거리 더해줌
				ans+=(dist*2);
				//남은 좌석 K로 초기화
				seat=K;
				//거리 초기화
				dist=0;
			}
			//현재 단지에 있는 학생이 모두 앉을 수 있는 경우
			if(arr[cur].cnt<=seat) {
				//남은 좌석에서 현재 단지의 학생 수를 빼줌
				seat-=arr[cur].cnt;
				//거리 갱신
				dist=Math.max(dist, Math.abs(S-arr[cur].pos));
			}
			//현재 단지에 있는 학생이 모두 앉을 수 없는 경우
			else {
				//거리 갱신
				dist=Math.max(dist,Math.abs(S-arr[cur].pos));
				//현재 단지 학생을 남은 좌석에 앉힐 수 있는 만큼 앉힘
				arr[cur].cnt-=seat;
				//왕복거리 더해줌
				ans+=(dist*2);
				//거리 갱신
				dist=Math.abs(S-arr[cur].pos);
				//현재 단지의 학생을 모두 태우기 위해 몫만큼 왕복
				int div=arr[cur].cnt/K;
				//div번 왕복하고 남은 학생 수
				int mod=arr[cur].cnt%K;
				ans+=(dist*div*2);
				//학생이 남지 않았은 경우
				if(mod==0) {
					dist=0;
					seat=K;
				}
				//남은 경우
				else {
					seat=K-mod;
				}
			}
			//왼쪽 탐색
			if(left)cur++;
			//오른쪽 탐색 
			else cur--;
			//모든 학생을 태운 단지 수 +1
			finish++;
		}
		//버스에 남은 학생이 있는 경우 dist에 0이 아닌 값이 있으므로 누적 합에 더해줌
		ans+=(dist*2);
		return ans;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken()),left=0;
		K=Integer.parseInt(st.nextToken());
		S=Integer.parseInt(st.nextToken());
		arr=new Point[N];
		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			int pos=Integer.parseInt(st.nextToken());
			int cnt=Integer.parseInt(st.nextToken());
			arr[i]=new Point(pos,cnt);
			if(pos<S)left++;
		}
		Arrays.sort(arr);
		//왼쪽, 오른쪽 이동 거리를 더해준 것이 정답
		System.out.println(search(0, left,true)+search(N-1, N-left,false));
	}
}