도서관 - 백준 1461 (Java)

 

 

https://acmicpc.net/problem/1461 

 

 

풀이

 1. 일단 양수 위치와 음수 위치의 책을 분리해서 그룹을 지었다. 왜냐하면 어차피 한 그룹 안에 지정되어도 한 쪽 갔다가 되돌아와서 0을 지나 다시 반대 쪽으로 갔다가 돌아오기 때문에 그룹으로 지정하는 의미가 없기 때문이다.

 

 2. 다음으로 고려한 부분은, 마지막에 모든 책을 제자리에 놔둔 후에는 0으로 돌아올 필요가 없기 때문에 절대값이 가장 큰 그룹을 마지막에 옮겨야한다. 

 

 3. 그리고 각 부호에서 가장 끝 수(가장 절대값이 큰 수)부터 그룹을 지었다. 

 예를 들면, 책이 3 6 8 20 25 위치에 있고 한 번에 옮길 수 있는 책이 2권이라 가정해보자. 만일 절대값이 가장 작은 수부터 그룹을 지으면 (3 6) (8 20) (25)가 된다. 이 때, 세준이에게 필요한 발걸음 수는 6*2 + 20*2 + 25 = 77이다. 반대로 절대값이 가장 큰 수부터 그룹을 지으면 (3) (6 8) (20 25)이므로 3*2 + 8*2 + 25 = 47이다.

 즉, 각 그룹에서 절대값이 큰 수의 2배만큼 걸음이 필요한데 절대값이 큰 수부터 그룹을 지으면 각 그룹의 절대값이 큰 수의 절대값 크기가 작아진다!

 

예시

 예제 2번으로 진행해보자.

최대 3권을 옮길 수 있으며, 책의 위치는 -18, -9, -4, 50,  22, -26 40, -45 이다.

 

오름차순 정렬하면, -45 -26 -18 -9 -4 22 40 50 이 되고 위에서 정한대로 그룹을 지어보면 (-45 -26 -18) (-9 -4) (22 40 50)이 된다. 여기서 절대값이 가장 큰 그룹은 세번째 그룹이므로 마지막에 진행한다. 따라서 최소 걸음 수는 45*2 + 9*2 + 50 = 158이다.

 

이를 코드로 옮기면 다음과 같다.

 

package src.baekjoon;

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

public class Main1461 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] bookArr = new int[N];

        st = new StringTokenizer(bf.readLine(), " ");

        //양수 개수
        int positive = 0;
        //음수 개수
        int negative = 0;

        for (int i = 0; i < N; i++) {
            int book = Integer.parseInt(st.nextToken());
            bookArr[i] = book;

            if(book<0) {
                negative++;
            } else {
                positive++;
            }
        }//for end

        //책 위치 오름차순 정렬
        Arrays.sort(bookArr);

        /**
         * 1. 각 부호에서 끝에서부터 최대 갯수로 그룹핑(음수:왼쪽부터, 양수:오른쪽부터) - 마지막 그룹은 남은 갯수만큼만 (다른 부호끼리는 그룹x)
         * 2. 각 그룹에서 절대값이 가장 큰 수의 2배만큼 이동거리 증가. 단, 그룹 대표 절대값 중 가장 큰 수는 1번만
         */
        int answer = 0;

        //음수
        int negativeIdx = 0;
        while (negativeIdx < negative) {
            answer -= bookArr[negativeIdx] * 2;
            negativeIdx += M;
        }//while end


        //양수
        int positiveIdx = N-1;
        while ((N-positive) <= positiveIdx) {
            answer += bookArr[positiveIdx] * 2;
            positiveIdx -= M;
        }//while end

        //양수 음수 그룹 중 절대값이 가장 큰 그룹은 1번 빼기
        answer = (-bookArr[0] < bookArr[N-1])? answer - bookArr[N-1] : answer + bookArr[0];

        System.out.println(answer);
    }
}