[PS] BOJ1461 도서관 ( greedy ) with JAVA

1461번: 도서관

 

 

◎ 문제풀이 

 

일직선상에서 책을 놓을 때 최소 걸음을 구하는 문제이다. 어떤 경우가 최소가 될 수 있는지 정확히 따져야 한다. 

 

 

 

 

최소 걸음으로 갈 수 있는 경우는 다음과 같다. 

 

1) 좌우를 번걸아 이동하면 안된다.

 

좌측으로 갔다가 우측으로 이동하면 0을 거친다. 0을 거치면 어차피 또 다시 책을 들고 갈 수 있으니 최소가 아니게 된다. 자료구조를 좌우로 분리하는 것이 좋다.

 

2) 가장 멀리 떨어져 있는 책을 가장 마지막에 놓아야 한다. 

 

마지막 조건을 보면 마지막에 책을 놓고 0으로 돌아오지 않아도 된다고 한다. 가장 멀리 있는 책을 가장 마지막에 놓아야 왕복을 하지 않아 최소가 된다. 

 

3) 가장 멀리 책들의 우선순위가 높아야 한다.

 

한번에 2권씩 옮길 수 있다고 가정하면 50과 37을 같이 옮겨야 37을 상쇄할 수 있다. 그러면 50 한번 갔다가 11로 가면 끝난다. 그런데 만약 37을 옮길때 11하고 같이 옮긴다면 37을 갔다가 50도 가야한다. 즉, 최소가 아니다. 가장 멀리있는 책들을 가장 먼저 m개로 묶어야 한다. 

 

이를 코드로 확인해보자. 

 

 

◎ 코드

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;

import static java.lang.Math.*;

//BOJ1461 도서관
public class Main {

    static int n;
    static int 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> leftBooks = new ArrayList<>(); // 좌측 책 리스트 
        List<Integer> rightBooks = new ArrayList<>(); // 우측 책 리스트

        st = new StringTokenizer(br.readLine());

        int rightMax = 0;
        int leftMax = 0;

        for(int i =0; i<n;i++){
             int value = Integer.parseInt(st.nextToken());
             
            // 좌우 측 분리 
             if(value < 0) {
                 leftMax = max(leftMax,abs(value));
                 leftBooks.add(abs(value)); // 음수는 절대값로 변환하여 넣기
             }
             else {
                 rightMax = max(rightMax,abs(value));
                 rightBooks.add(value);
             }
        }
        
        // 가장 멀리 있는 책들을 우선 묶기 위해 내림차순으로 정렬
        Collections.sort(leftBooks,Collections.reverseOrder());
        Collections.sort(rightBooks,Collections.reverseOrder());

        // 가장 멀리 있는 책을 가장 마지막에 방문하기 위해, 좌측 리스트와 우측 리스트의 최대 거리를 비교하여 메소드 호출
        int ans =0;
        if(leftMax > rightMax) ans = getStepCount(rightBooks,leftBooks);
        else ans = getStepCount(leftBooks,rightBooks);

        System.out.println(ans);

    }

    public static int getStepCount(List<Integer> firstBooks, List<Integer> secondBooks){
        int result = 0;

        int pointer = 0;
        while(pointer < firstBooks.size()){ // 멀리 있는 것부터 m개씩 묶기
            result += firstBooks.get(pointer)*2; // 왕복
            pointer += m; // m 개씩 묶기
        }

        pointer = 0;
        while(pointer < secondBooks.size()){
            if(pointer == 0) result += secondBooks.get(pointer); // 가장 멀리 있는 책은 한번만 왕복X
            else result += secondBooks.get(pointer)*2; // 그외 책은 왕복
            pointer += m; // m개식 묶기
        }

        return result;
    }
}