[1461] 도서관

[Gold V] 도서관 - 1461

문제 링크

성능 요약

메모리: 14244 KB, 시간: 124 ms

분류

그리디 알고리즘, 정렬

문제 설명

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

입력

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

출력

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

아이디어

결국 최소 걸음으로 책을 가져다놓기 위해서는 가장 멀리 떨어져있는 책을 가장 나중에 가져다놔야한다.(다시 돌아올 필요가 없기 때문) 또, 양쪽으로 좌표가 주어지기 때문에 가장 멀리 떨어져있는 책이 왼쪽에 있는지, 오른쪽에 있는지도 파악해야한다.
자세한 풀이는 주석을 보자.

답안코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        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());    // 한 번에 들 수 있는 책의 개수

        List<Integer> leftSide = new ArrayList<>();
        List<Integer> rightSide = new ArrayList<>();

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

            if (bookPoint < 0) {
                leftSide.add(bookPoint * (-1));
            } else {
                rightSide.add(bookPoint);
            }
        }

        // 멀리 떨어져있는 책들을 최대한 한 번에 많이 들고 가야하기 때문에 내림차순 정렬해준다.
        rightSide.sort((i1, i2) -> i2 - i1);    // 내림차순 정렬
        leftSide.sort((i1, i2) -> i2 - i1);    // 내림차순 정렬

        int steps = 0;

        // 한 번에 들 수 있는 책의 수(m) 만큼 증가시키며 step을 계산한다.
        for (int i = 0; i < rightSide.size(); i+=m) {
            steps += rightSide.get(i) * 2;
        }
        for (int i = 0; i < leftSide.size(); i+=m) {
            steps += leftSide.get(i) * 2;
        }

        // 가장 멀리 떨어진 경우를 한 번 더 세주었으므로 총 step에서 빼준다.
        if (rightSide.size() == 0 || (leftSide.size() != 0 && rightSide.get(0) < leftSide.get(0))) {
            steps -= leftSide.get(0);
        } else if (leftSide.size() == 0 || (rightSide.size() != 0 && rightSide.get(0) > leftSide.get(0))) {
            steps -= rightSide.get(0);
        }

        System.out.println(steps);
    }
}

BOJ 카테고리 내 다른 글 보러가기