백준 1461 : 도서관

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

1461번: 도서관

[ 문제풀이 ]

최소 걸음을 구하는 것이기 때문에 가장 먼 곳에 있는 책은 마지막에 옮겨야 한다. 마지막에는 0으로 돌아올 필요가 없기 때문이다.

또한, 책 한개를 옮길 때 M개의 책을 함께 옮길 수 있으니 남은 책들중에서 거리가 먼 책을 먼저 옮겨야 한다.

따라서 두 조건 모두 거리가 먼 책이 우선순위가 높기 때문에 정렬을 먼저 해준다.

정렬전: -37 2 -6 -39 -29 11 -28
정렬후: -39 -37 -29 -28 -6 2 11

 

잘 생각해보면 시작점은 항상 0이기 때문에 음수(양수)->양수(음수)->0으로 이동하는 것은 음수(양수)->0, 양수(음수)->0으로 이동하는 것과 동일하다.

따라서 양수와 음수를 나눠서 가장 거리가 큰 책을 기준으로 M개씩 옮겨주면 해결할 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int[] book = new int[N];
			st = new StringTokenizer(br.readLine());

			List<Integer> minus = new ArrayList<>();
			List<Integer> plus = new ArrayList<>();
			for (int i = 0; i < N; ++i) {
				book[i] = Integer.parseInt(st.nextToken());
				if (book[i] < 0) minus.add(-book[i]);
				else plus.add(book[i]);
			}
			
			Collections.sort(minus, Collections.reverseOrder());
			Collections.sort(plus, Collections.reverseOrder());
			
			int answer = 0, posMinus = 0, posPlus = 0;
			
			//가장 먼 책을 기준으로 M개를 반납(돌아오지 않음)
			if (plus.isEmpty()) {
				answer += minus.get(posMinus);
				posMinus += M;
			} else if (minus.isEmpty()) {
				answer += plus.get(posPlus);
				posPlus += M;
			} else {
				if (minus.get(posMinus) >= plus.get(posPlus)) {
					answer += minus.get(posMinus);
					posMinus += M;
				} else {
					answer += plus.get(posPlus);
					posPlus += M;
				}
			}
			
			//모든 책을 반납할때까지 가장 먼 책을 기준으로 M개의 책을 반납(돌아옴)
			while (posMinus < minus.size()){
				answer += minus.get(posMinus) * 2;
				posMinus += M;
			}
			while (posPlus < plus.size()){
				answer += plus.get(posPlus) * 2;
				posPlus += M;
			}
			bw.write(answer + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}