[BAEKJOON]1461 도서관

문제 요약

• 알고리즘 분류: 그리디, 정렬, 힙
• 난이도:Gold5
• 문제내용:
  • N개의 책과 최대 들고갈수 있는 책의 개수 M이 있다.
  • 모든 책을 갔다 놓을수 있도록 최소 거리를 구해라(다시 돌아올 필요는 없다.)
• 사이트: https://www.acmicpc.net/problem/1461

 

문제풀이

 이번 문제는 그리디와 힙을 응용해야 되는문제이다. 그리디 알고리즘 약간 아이디어 문제측에 속한다. 정답을 어떻게 구할지만 구현은 쉽다. 그리디와 힙에 대한 설명은 아래의 사이트에서 확인해보면된다.

• 그리디: https://jih3508.tistory.com/70
• 힙: https://jih3508.tistory.com/81

문제 접근 방법

 이번 그리디 관련한 문제는 음수영역과 양수 영역을 따로 구분해서 책을 꽃아야 한다.  그러기 위해서는 음수영역과 양수 영역을 따로 구분 한 다음 음수 영역은 오름차순/MinHeap, 양수정렬은 내침차순/MaxHeap 정렬을 해서 각 영역에서 M개씩 묶어서 M개중 가장 거리가 먼 것끼리 합하면 된다.

 

 예제 1번을 그림으로 나타 낸것이다. 문제에 따라서 2개씩 들고 갈수 있기 때문에 음수쪽 영역에서 2개씩 묶고 양수쪽에도 2개씩 묶는다. 그 노란 책 칠한 부분은 들고갈수 있는 거리중 가장 먼 곳이다. 왔다갔다 하면 절대값(거리) * 2이다. 그다음 문제에서는 책을 다 꽃고 다시 원래 위치로 돌아 올 필요가 없다. 그래서 최단 거리를 구할라면 가장 먼곳을 맨 마지막에 가면 된다. 그러면 총 이동한 거리구한 다음 가장 먼곳을 빼면 끝이다. 결론으로 출력해야 될 식은 절대값(거리) * 2 - 가장 먼 거리이다.

 정리

1. 음수영역은 왼쪽, 양수 영역은 오른쪽 힙/ 배열을 선언한다.
2. 음수영역은 MinHeap/내침차수, 양수 영역은 MaxHeap/오름차순 으로 데이터를 넣는다.
3. 음수영역, 양수 영역  0부터 M개 단위로 이동해서 합을 구한다.
4. 총이동한 거리에 *2하고 음수영역, 양수 영역중 가장 먼것을 뺀다.

Code

리스트/배열 정렬로 구현

Python

N, M = map(int, input().split())
books = sorted(list(map(int, input().split())))

left = []
right= []
for book in books:
    if book < 0:
        left.append(-book)
    else:
        right.append(book)

right.reverse()

print((sum(left[::M]) + sum(right[::M])) * 2 - max(left + right))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		List<Integer> right = new ArrayList<>();
		List<Integer> left = new ArrayList<>();
		int book;
		int max = 0;
		for(int i = 0; i < N; i++) {
			book = Integer.parseInt(st.nextToken());
			// 음수는 양수로 변환
			if(book < 0) {
				left.add(-book);
			}else {
				right.add(book);
			}
			max = Math.max(max, Math.abs(book));
		}
				
		Collections.sort(left, Collections.reverseOrder());
		Collections.sort(right, Collections.reverseOrder());
		
		// 각 거리 합 구하기
		int sum = 0;
		for(int i = 0; i < left.size(); i+=M) {
			sum += left.get(i) * 2;
		}
		
		for(int i = 0; i < right.size(); i+=M) {
			sum += right.get(i) * 2;
		}
		System.out.println(sum - max);
	}
	
}

Heap으로 구현

Python

import heapq
N, M = map(int, input().split())
books = sorted(list(map(int, input().split())))

left = []
right= []
max_move = 0 # 최대 거리
for book in books:
    if book < 0:
        heapq.heappush(left, book)
    else:
        heapq.heappush(right, -book)
    max_move = max(max_move, abs(book))

move = 0 # 총 이동거리

# 왼쪽, 오른쪽 거리 구하기
for i in range(len(left)):
    num = - heapq.heappop(left)
    if i % M == 0:
        move += num * 2

for i in range(len(right)):
    num = - heapq.heappop(right)
    if i % M == 0:
        move += num * 2

print(move - max_move)

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException{
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		PriorityQueue<Integer> left = new PriorityQueue<Integer>();
		PriorityQueue<Integer> right = new PriorityQueue<Integer>();
		int book, index;
		int max_move = 0;
		
		// 좌우에 위치에 따라서 heap에 저장
		for(int i = 0; i < N; i++) {
			book = Integer.parseInt(st.nextToken());
			if(book < 0) {
				left.add(book);
			}else {
				right.add(-book);
			}
			max_move = Math.max(max_move, Math.abs(book));
		}
		
		index = 0;
		int move = 0;
		while(!left.isEmpty()) {
			book = left.poll();
			if(index % M == 0) {
				move += -book * 2;
			}
			index++;
		}
		
		index = 0;
		while(!right.isEmpty()) {
			book = right.poll();
			if(index % M == 0) {
				move += -book * 2;
			}
			index++;
		}
		
		System.out.println(move - max_move);
	}
	
}