백준 1461번: 도서관 (Python/Java)

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

1461번: 도서관

 

 

 

접근

---

처음 풀려고 했던 방식은 가장 거리가 먼 구역을 한 번만 가도록, 즉 가장 마지막에 갈 곳만 생각했다. 그래서 그냥 간단하게 구역을 한 번에 옮길 수 있는 책의 개수로 묶고, 가장 먼 곳을 마지막에 가게끔 구현했다. 하지만 그렇게 풀면 절대 최소 거리가 나올 수 없다는 것은 금방 눈치챌 수 있었다.

 

예제 1번을 기준으로 생각해보자. 구역을 책의 개수 2개로 나눠보자. 물론 거리가 음수인 구역과 양수인 구역은 따로 나눠서 묶어야 한다. 나 같은 경우는 2차원 배열로 만들어 음수 위치와 양수 위치를 따로 저장했다. 그 결과 (-6, -28), (-29, -37), (-39), (2, 11) 이렇게 세 개로 나눠지는 것을 확인할 수 있다. 이를 기준으로 가장 먼 곳인 -39를 마지막으로 가게끔 계산해보면 191이 나온다. 정답 131 하고 차이가 굉장히 크게 난다. 방식 자체가 틀린 건 아니지만 어떻게 위치를 묶느냐에서 큰 실수가 있었기 때문이다.

 

해당 문제의 키포인트는 가장 먼 곳이 나머지로 묶이는 것이 아니라, 가장 짧은 곳이 나머지로 묶여야 한다는 것이다. 무슨 의미냐면, 위의 방법에서는 거리가 가장 가까운 -6부터 묶어 나가기 시작해서 마지막 -39는 하나만 따로 구역으로 설정된다. 이게 아니라 가장 먼 -39부터 묶기 시작해서  (-39, -37), (-29, -28), (-6) 이렇게 묶어야 한다. 이제 각 구역당 더 높은 구역과 원점을 오가며 책을 가져다 놔야 최소 걸음 수로 책을 가져다 놓을 수 있다.(양수 부분 구역 또한 똑같은 방식으로 구현하면 된다.)

 

마지막으로 생각해봐야 할 부분은 다시 돌아오지 않아도 되는 마지막 책 위치다. 아래 코드에서는 모든 걸음걸이는 2를 곱해 더해줬다.(한번 갔다가 다시 와야 하니까 걸음이 두배로 필요하다) 하지만 가장 마지막에 책을 놓으면 다시 돌아오지 않아도 되기 때문에 문제가 생긴다. 이 부분은 복잡하게 생각할 필요 없다. 양수 부분의 최대 거리와 음수 부분의 최대 거리를 비교하고 더 큰 값을 한번 빼주면 된다.

 

 

 

풀이

---

Python

def listSplit(idxList, leng):
    return [idxList[i : i+leng] for i in range(0, len(idxList), leng)]

allBook, moveBook = map(int, (input()).split())

firstLine = (input()).split()
bookList = [[], []]
for i in range(allBook):
    if int(firstLine[i]) < 0:
        bookList[0].append(int(firstLine[i])*-1)
    else:
        bookList[1].append(int(firstLine[i]))
bookList[0].sort(reverse=True)
bookList[1].sort(reverse=True)

result, rightMax, leftMax = 0, 0, 0

leftList = listSplit(bookList[0], moveBook)
for i in range(len(leftList)):
    result += leftList[i][0]*2
    leftMax = max(leftMax, leftList[i][0])

rightList = listSplit(bookList[1], moveBook)
for i in range(len(rightList)):
    result += rightList[i][0]*2
    rightMax = max(rightMax, rightList[i][0])
    
if leftMax <= rightMax:
    result -= rightMax
else:
    result -= leftMax

print(result)

 

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        int allBook = Integer.parseInt(firstLine[0]), moveBook = Integer.parseInt(firstLine[1]);

        String[] secondLine = (scan.nextLine()).split(" ");
        ArrayList<Integer>[] bookList = new ArrayList[2];
        bookList[0] = new ArrayList<Integer>();
        bookList[1] = new ArrayList<Integer>();
        for(String idx : secondLine){
            if(Integer.parseInt(idx) < 0){
                bookList[0].add(Integer.parseInt(idx)*-1);
            }else{
                bookList[1].add(Integer.parseInt(idx));
            }
        }
        Collections.sort(bookList[0], Collections.reverseOrder());
        Collections.sort(bookList[1], Collections.reverseOrder());

        int result = 0, rightMax = 0, leftMax = 0;

        ArrayList<ArrayList<Integer>> leftList = listSplit(bookList[0], moveBook);
        for(int i = 0 ; i < leftList.size() ; i++){
            result += (leftList.get(i)).get(0)*2;
            leftMax = Math.max(leftMax, (leftList.get(i).get(0)));
        }
        
        ArrayList<ArrayList<Integer>> rightList = listSplit(bookList[1], moveBook);
        for(int i = 0 ; i < rightList.size() ; i++){
            result += (rightList.get(i)).get(0)*2;
            rightMax = Math.max(rightMax, (rightList.get(i).get(0)));
        }

        if(leftMax <= rightMax){
            result -= rightMax;
        }else{
            result -= leftMax;
        }

        System.out.println(result);

    }

    private static ArrayList<ArrayList<Integer>> listSplit(ArrayList<Integer> idxList, int leng){

        ArrayList<ArrayList<Integer>> splitList = new ArrayList<ArrayList<Integer>>();

        for(int i = 0 ; i < idxList.size() ; i += leng){
            ArrayList<Integer> subList = new ArrayList<Integer>();
            for(int j = i ; j < (i+leng) ; j++){
                if(j < idxList.size()){
                    subList.add(idxList.get(j));
                }
            }
            splitList.add(subList);
        }

        return splitList;

    }

}

 

 

 

후기

---

어떤 식으로 오고 갈지 방식을 생각할 때는 그렇게 오래 걸리지 않았지만 이를 구현하는 과정에서 시간이 조금 걸렸다. 위치가 담긴 배열에서 for문, while문을 써가며 시도해봤는데, 그렇게 어려운 부분이 아님에도 불구하고 하면 할수록 코드가 복잡해지고 읽기가 힘들어졌다. 결국에는 한 번에 옮길 수 있는 책의 개수를 기준으로 배열을 다시 나눠줬다. 조금 더 간결하게 해결하고 싶었는데 이렇게 푸니 풀고 나서도 영 만족스럽지 못하고 찝찝한 기분이다. 

 

또, 막상 배열을 자르려고 하니 '배열을 어떻게 자르더라...' 싶었다. 생각해보니 이상하게도 배열을 잘라서 다시 배열로 묶어준 기억이 별로 없었다. 그렇게 특이한 경우도 아닌데 왜 여태 그런 적이 없었지 싶더라. 혹시 파이썬과 자바에서 함수로 지원해주나 싶어 찾아보니 따로 지원해주는 함수는 없고 직접 구현해야 했다. 함수 찾아보다가 배열을 여러 개로 나누는 방식을 구현한 글을 우연히 발견해서(https://jsikim1.tistory.com/141) 조금 참고했다.

 

구현 문제를 조금 더 풀어보며 머릿속에 있는 방법을 코드로 풀어내는 능력을 키워야겠다.