1461번 : 도서관

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	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());
		int M = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		PriorityQueue<Integer> positive = new PriorityQueue<Integer>();
		PriorityQueue<Integer> negative = new PriorityQueue<Integer>(Collections.reverseOrder());
		int num;
		for(int i=0;i<N;i++) {
			num = Integer.parseInt(st.nextToken());
			if(num > 0) {
				positive.offer(num);
			}
			else {
				negative.offer(num);
			}
		}
		int result = 0;
		int max = 0;
		int pos_size = positive.size(), neg_size = negative.size();
		if(pos_size > M) {
			for(int i=0;i<pos_size%M;i++) {
				max = positive.poll();
			}
			result += max*2;
			max = 0;
			pos_size = positive.size();
			for(int i=0;i<pos_size/M-1;i++) {
				for(int j=0;j<M;j++) {
					max = positive.poll();
				}
				result += max*2;
			}
		}
		max = 0;
		if(neg_size > M) {
			for(int i=0;i<neg_size%M;i++) {
				max = negative.poll();
			}
			result -= max*2;
			max = 0;
			neg_size = negative.size();
			for(int i=0;i<neg_size/M-1;i++) {
				for(int j=0;j<M;j++) {
					max = negative.poll();
				}
				result -= max*2;
			}
		}
		int left = 0, right = 0;
		pos_size = positive.size();
		if(positive.size() > 0) {
			for(int i=0;i<pos_size;i++) {
				left = positive.poll();
			}
		}
		neg_size = negative.size();
		if(negative.size() > 0) {
			for(int i=0;i<neg_size;i++) {
				right = negative.poll();
			}
		}
		right = -1 * right;
		result += Math.min(left, right)*2;
		result += Math.max(left, right);
		System.out.println(result);
		br.close();
	}
}

 

포스팅 시작 후 첫 골드문제입니다.

 

0에서부터 출발해 수직선 상의 좌표를 최대 M개 까지 방문할 수 있을 때 최단 경로를 구하는 문제인데요,

 

0을 사이에 두고 +,- 사이를 왔다갔다 하는 움직임이 최단경로에 포함될지의 여부를 생각하면 꽤 골치아파집니다.

 

결론부터 말하면, 0을 방문하는 순간 항상 M이 초기화되기 때문에 왔다갔다 하는 움직임은 최단경로를 만드는 데 전혀 도움이 되지 않습니다.

 

최단경로를 만드는 방법은, 음수와 양수 방향으로 모두 M개 씩만 방문할 수 있기 때문에, 어느 방향으로 M개보다 많을 경우 M으로 나눈 나머지만큼을 미리 왕복해서 개수를 M의 배수로 만들고, 개수 / M-1번 왕복해서 양쪽 다 한번만 가면 되는 상태를 만든 후 음수와 양수 중 더 먼 쪽을 한번만 가도 되도록 마지막에 방문하면 됩니다.

 

여기까지 생각했다면 구현 자체는 그렇게 어렵지는 않은데 우선순위 큐를 이용해서 양수와 음수가 절댓값이 작은 순서대로 정렬되게 만든 후(음수의 경우 반대로 정렬해야 합니다), 위에서 계산한 대로 큐에서 원소를 뽑아 왕복해서 결과를 result에 더해주면 됩니다.

 

실수하기 쉬운 포인트는 위의 코드에서 max에 해당하는 중간중간의 이동거리를 저장하는 변수를 계속 초기화해서 0에서 시작해야 한다는 부분과 큐의 사이즈를 for문에 이용할 때 큐의 size메서드를 쓰면 중간에 사이즈가 바뀌기 때문에 따로 변수에 저장해서 사용해야 한다는 부분입니다.