백준1461 도서관 문제 풀이 - java

백준1461 도서관 문제 풀이 - java

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

1461번: 도서관

 

도서관 성공

문제

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

입력

첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 책의 위치는 0이 아니며, 절댓값은 10,000보다 작거나 같은 정수이다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 1 

7 2
-37 2 -6 -39 -29 11 -28

예제 출력 1 

131

 

풀이

• -2 -1 1 2 이고 M = 2일때  (-2, -1) , (1, 2) 묶음으로 배달하면 된다
• -4 -3 -2 -1 이고 M = 2일때 (-4, -3), (-2, -1) 묶음으로 배달하면 된다
• -4, -2 묶음으로 배달하는것은 손해다 
• 그리고 마지막 책배달을 마치고 0 위치로 복귀할 필요가 없기 때문에 가장 먼위치의 책은 마지막에 one_way 배달하고 나머디는 two_way 배달한다.
• PQ를 사용했고 0을 기준으로 음수영역과 양수 영역을 나눠서 계산했다.

package B1461;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * https://www.acmicpc.net/problem/1461
 * title : 도서관 Gold V
 * @author tempcru
 * 
 */
public class Main {

	static long result;
	
	// N, M : [1, 50]
	static int N, M;
	
	static PriorityQueue<Integer> f_book;
	static PriorityQueue<Integer> b_book;
	
	public static void main(String[] args) throws Exception {

//		System.setIn(new FileInputStream("./src/B1461/sample_data"));
//		7 2
//		-37 2 -6 -39 -29 11 -28
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		

		StringTokenizer st = new StringTokenizer(br.readLine().trim());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		Comparator comp_max = new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2 - o1;
			}
		};
		
		f_book = new PriorityQueue<Integer>(comp_max);
		b_book = new PriorityQueue<Integer>(comp_max);
		
		st = new StringTokenizer(br.readLine().trim());
		
		int temp = 0;
		for(int i = 0; i < N; i++) {
			temp = Integer.parseInt(st.nextToken());
			if (temp < 0) {
				temp *= -1;
				f_book.add(temp);
			}else {
				b_book.add(temp);
			}
		}
		
		one_way_case();
		two_way_case();
		
		System.out.println(result);
			
	}

	private static void two_way_case() {
		while (!f_book.isEmpty() || !b_book.isEmpty()) {
			
			if(f_book.isEmpty()) {
				result+= 2 * bbook_peek_poll();
				continue;
			}
			
			if(b_book.isEmpty()) {
				result+= 2 * fbook_peek_poll();
				continue;
			}
			
			if (f_book.peek() > b_book.peek()) {
				result+= 2 * fbook_peek_poll();
				continue;
			} else {
				result+= 2 * bbook_peek_poll();
				continue;
			} 
		}
	}

	private static void one_way_case() {
		if(f_book.isEmpty()) {
			result+= bbook_peek_poll();
		} else if(b_book.isEmpty()) {
			result+= fbook_peek_poll(); 
		} else if (f_book.peek() > b_book.peek()) {
			result += fbook_peek_poll(); 
		} else {
			result += bbook_peek_poll();
		}
	}

	private static long fbook_peek_poll() {
		int peek = f_book.peek();
		for (int i = 0 ; i < M; i++) {
			if(!f_book.isEmpty()) {
				f_book.poll();
			}
		}
		return peek;
	}
	
	private static long bbook_peek_poll() {
		int peek = b_book.peek();
		for (int i = 0 ; i < M; i++) {
			if(!b_book.isEmpty()) {
				b_book.poll();
			}
		}
		return peek;
	}
}