[Java] 백준 1461 도서관

문제

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

 

입력

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

 

출력

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

 

문제 링크 : 도서관

---

설명

문제는 간단하다.

그리디 알고리즘을 사용해서 푸는 문제이고, 정렬을 하면 쉽게 풀 수 있다.

 

일단 이 문제를 손으로 그려보면 제일 먼 거리를 왕복하지 않는 것이 최선임을 알 수 있다.

그리고 음수가 나오니 나는 양수 배열과 음수 배열로 나눠서 풀었다.

 

그리고 내림차순 정렬을 하여 제일 먼거리부터 k개 책을 한번에 가는 방식으로 풀었다.

*2 를 해준 이유는 그 거리만큼 갔다가 다시 0으로 돌아와야하기 때문에 그 거리만큼 다시 와야해서 *2를 해준 것이다.

 

마지막에 제일 먼 거리는 왕복이 아닌 한번만 가면 되므로 - last 를 해준다.

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());

        Integer[] plus, minus; plus = new Integer[n]; minus = new Integer[n]; // 양수, 음수
        int last = 0; int ans = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n;i++){
            Integer now = Integer.parseInt(st.nextToken());

            if (now > 0) {
                plus[i] = now; 
                minus[i] = 0; // Integer 은 값이 없을 경우 null을 저장함. 그래서 0을 넣어줌.
            }
            else {
                minus[i] = Math.abs(now);
                plus[i] = 0;
            }

            last = Math.max(last, Math.abs(now)); // 제일 먼 거리 저장
        }
        // 제일 먼 거리가 먼저 오게 내림차순 정렬
        Arrays.sort(plus, Collections.reverseOrder());
        Arrays.sort(minus, Collections.reverseOrder());

        for (int i = 0; i < plus.length; i+= m){
            if (plus[i] == 0) break; // 현재 값이 0이라는 의미는 책이 없다는 의미 이므로 종료
            ans += plus[i] * 2; // 갔다가 다시 돌아오는 거리
        }
        for (int i = 0; i < minus.length; i+= m){
            if (minus[i] == 0) break; // 현재 값이 0이라는 의미는 책이 없다는 의미 이므로 종료
            ans += minus[i] * 2; // 갔다가 다시 돌아오는 거리
        }
        System.out.println(ans - last); // 총 거리 - 제일 먼거리(왕복 x)
    }
}