[백준] 1461번 도서관 (Java)

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

 

스터디원이 추천해 줘서 알게 된 전형적인 그리디 문제이다.

처음 접근할 때는 가장 작은 음수값과 가장 큰 양수값을 미리 빼놓고 거리 계산에 미포함시키려고 했는데 이 경우는 항상 최적의 답이 안 나온다. 그 이유는 편도로 가는 길에 M개의 책을 놓을 수 있는데, 편도로 가면 무조건 한 개만 놓을 수 있다고 잘못 생각했기 때문이다..

그리디 문제인 것만 눈치채면 정렬과 분기처리로 어렵지 않게 풀 수 있다.

---

import java.io.*;
import java.util.*;

public class Main {
	static int N, M;
	static PriorityQueue<Integer> minus;
	static PriorityQueue<Integer> plus;
	static int answer = 0;
	static int min = 0, max = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		minus = new PriorityQueue<>();
		plus = new PriorityQueue<>((a, b) -> b - a);

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			int number = Integer.parseInt(st.nextToken());
			if (number < 0) {
				minus.add(number);
			} else {
				plus.add(number);
			}
		}

		if (!minus.isEmpty()) {
			min = Math.abs(minus.peek());
		}
		if (!plus.isEmpty()) {
			max = plus.peek();
		}

		while (minus.size() >= M) {
			answer += Math.abs(minus.poll()) * 2;
			for (int i = 0; i < M - 1; i++) {
				minus.poll();
			}
		}

		if (!minus.isEmpty()) {
			answer += Math.abs(minus.poll()) * 2;
		}

		while (plus.size() >= M) {
			answer += plus.poll() * 2;
			for (int i = 0; i < M - 1; i++) {
				plus.poll();
			}
		}

		if (!plus.isEmpty()) {
			answer += plus.poll() * 2;
		}

		if (min > max) {
			answer -= min;
		} else {
			answer -= max;
		}

		System.out.println(answer);
	}
}