[백준] 1461 도서관

문제

---

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

 

 

 

 

풀이

---

탐욕알고리즘을 통해서 문제를 풀었다.

 

책의 위치가 뒤죽박죽 주어지기 때문에 음수위치의 책은 오름차순, 양수위치의 책은 내림차순으로 우선 정렬을 해주었다.

가장 거리가 먼 책을 한번만 방문하는 것이 유리하기 때문에, 우선 절대값을 기준으로 값을 오름차순으로 정렬하였다.

 

알고리즘 순서는 아래와 같다.

1. 순서대로 m 개씩 반복문을 움직이며 값을 *2 한 값을 더해준다. 음수의 책과 양수의 책을 이동시켜준다. 음수와 양수 둘은 따로 해야한다. (시작점은 0이라고 했기 때문)
2. 가장 절대값이 큰 수를 빼준다.(마지막으로 방문하고 끝내게 하기 위해)

위 순서를 코드로 구현하면 아래와 같다.

int answer = 0;
for(int i = 0 ; i < Lbook.size() ; i+= m){
	answer += Math.abs(Lbook.get(i)) * 2;
}

for(int i = 0 ; i < Rbook.size() ; i += m) {
	answer += Rbook.get(i) * 2;
}


answer -= absBook.get(0);

음수 양수 각각 m 씩 더해주면서 책의 위치 *2 를 더해준다. 최대한 책을 많이 가지고 이동하는 것이 유리하기 때문이다.

 

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static List<Integer> Lbook, Rbook, absBook;
	static int n, m;
			
	static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		n = parseInt(st.nextToken());
		m = parseInt(st.nextToken());
	
		Lbook = new ArrayList<>();
		Rbook = new ArrayList<>();
		absBook = new ArrayList<>();
		
		st = new StringTokenizer(bufferedReader.readLine());
		for(int i = 0 ; i < n ; i++) {
			int book = parseInt(st.nextToken());
			if(book < 0) {
				Lbook.add(book);
			}
			else {
				Rbook.add(book);
			}
			
			absBook.add(Math.abs(book));
		}
		
		Collections.sort(Lbook);
		Collections.sort(Rbook, Collections.reverseOrder());
		Collections.sort(absBook, Collections.reverseOrder());
		
		
		int answer = 0;
		for(int i = 0 ; i < Lbook.size() ; i+= m){
			answer += Math.abs(Lbook.get(i)) * 2;
		}
		
		for(int i = 0 ; i < Rbook.size() ; i += m) {
			answer += Rbook.get(i) * 2;
		}
		
		
		answer -= absBook.get(0);
	
		System.out.println(answer);
	}
}