[백준] BOJ 1461 도서관 (골드 4)

문제

---

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

1461: 도서관

---

해설

---

1. 음수 -> 양수, 양수 -> 음수로 이동하는 경우는 어차피 0을 지나가므로
   새로운 책을 들고 갈 수 있게 되므로 양수, 음수를 나누어서 판단한다.
   
   
2. 기본적으로 절대값이 큰 값을 우선으로 정렬한다.
   이유 : 멀리 있는 책을 가져다 둘 때 더 작은 값을 M-1개 들고갈 수 있다는 아이디어.
   
   
3. 즉, M개의 책을 가지고 가는데 가장 멀리있는 책의 왕복거리만큼 이동거리를 더해주면
   M-1개의 책은 가져다둘 때 가는 길에 두고 올 수 있으므로 거리를 더해줄 필요가 없다.
   
   
4. 따라서 getSum 메서드에 cnt == 0인경우에만 왕복거리를 더해준다.
   
   
5. 하지만, 마지막에 0으로 돌아오지 않아도 되므로,
   음수와 양수 중 절대값이 가장 큰 경우를 마지막에 둔다고 생각하면
   가장 멀리 있는 거리는 이동 거리만 더해주면 된다 (왕복 거리 - 이동거리 로 구현)

---

코드 (그리디)

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M;
    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());

        List<Integer> negatives = new ArrayList<>();
        List<Integer> positives = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            if (num < 0) {
                negatives.add(-num);
            } else {
                positives.add(num);
            }
        }

        //음수, 양수 기준으로 절대값이 큰 값 기준으로 정렬
        Collections.sort(negatives, Collections.reverseOrder());
        Collections.sort(positives, Collections.reverseOrder());


        int sum = getSum(positives) + getSum(negatives);
        int end = 0;
        if (!positives.isEmpty() && !negatives.isEmpty()) {
            end = Math.max(positives.get(0), negatives.get(0));
        } else if (positives.isEmpty()) {
            end = negatives.get(0);
        } else {
            end = positives.get(0);
        }
        System.out.println(sum - end);
    }

    private static int getSum(List<Integer> numbers) {
        int cnt = 0;
        int sum = 0;
        for (Integer number : numbers) {
            if (cnt == 0) sum += (number * 2); //왕복 거리
            if (++cnt == M) cnt = 0;
        }
        return sum;
    }
}

---

결론

---

0을 기준으로 음수 -> 양수, 양수 -> 음수를 나눠서 생각하는 것과

마지막에 0으로 돌아오지 않아도 되므로 이를 효율적으로 사용하기 위한 아이디어가 중요했던 문제

---