白駿1461、図書館-Greedy

1.アイデア

2.資料構造

3.時間複雑度

コード#コード#

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

public class Main {
	static int n, m;			// 책의 개수 n, 한 번에 들 수 있는 책 최대 개수 m
	static List<Integer> plusPosList = new ArrayList<>();
	static List<Integer> minusPosList = new ArrayList<>();
	static int maxDistPos;		// 원점으로부터 가장 먼 거리의 위치
	static int minStep;			// 출력, 최소 걸음 수

	static void solution() {
		// 거리가 먼 순으로 m개 씩 원점을 왕복하며(거리 x 2) minStep 에 더함
		while (!plusPosList.isEmpty()) {
			// 한 번에 최대 m개 책 이동
			for (int i = 0; i < m; i++) {
				if (plusPosList.isEmpty())
					break;

				// 왕복 이동 거리: m개 책 묶음에서, 첫 번째 가장 먼 책의 거리 x 2
				if (i == 0)
					minStep += plusPosList.get(0) * 2;
				plusPosList.remove(0);
			}
		}

		while (!minusPosList.isEmpty()) {
			// 한 번에 최대 m개 책 이동
			for (int i = 0; i < m; i++) {
				if (minusPosList.isEmpty())
					break;

				// 왕복 이동 거리: m개 책 묶음에서, 첫 번째 가장 먼 책의 거리 x 2
				if (i == 0)
					minStep += -(minusPosList.get(0)) * 2;
				minusPosList.remove(0);
			}
		}

		// 마지막에 옮기는 가장 먼 책은 왕복 X (위에서 왕복 처리한 거리를 다시 빼줌)
		minStep -= Math.abs(maxDistPos);
	}

	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());
		st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			int pos = Integer.parseInt(st.nextToken());

			if (Math.abs(maxDistPos) < Math.abs(pos))
				maxDistPos = pos;

			if (pos > 0)
				plusPosList.add(pos);
			else
				minusPosList.add(pos);
		}

		// 원점으로부터 거리 먼 순(절댓값 큰 순)으로 정렬
		Collections.sort(plusPosList, Collections.reverseOrder());
		Collections.sort(minusPosList);

		solution();
		System.out.println(minStep);
	}
}