[자바/백준 골드5] #1461 도서관

🔒 골드5 - #1461 도서관

 

📌 테스트케이스 추가 힌트

5 2
1 2 3 4 5

= 13

5 2
-45 -26 -18 -9 -4

= 89

5 3
-45 -26 -18 -9 -4

= 63

 

✍️ 풀이법

 

해당 문제는, 문제를 이해하기와 테스트케이스가 풀어지는 과정을 구하는 것이 다소 어려웠다.

 

당연히 2개씩 책을 들고 간다면, 끝부터 차례로 2개씩 놓으면 된다고 생각을 했는데 답이 도출되지 않았고,

중간에 책을 놓고 가는 경우를 생각 해보니 답이 도출되었지만, 식을 세우기 어려웠다.

 

따라서 다시 답이 도출되는 과정을 생각해 보고 문제를 해결하였다.

 

 

 

 

내가 생각한 답이 도출되는 과정은 한 칸씩 전진하는 방법이다.

한칸씩 움직이면서, 해당 방향에 있는 모든 책들을 옮기는 방식으로 진행하면된다.

 

위의 테스트케이스를 예로 들면,

5 2
1 2 3 4 5

= 13

 

가로축은 좌표를, 네모박스는 책을 의미한다면, 처음에는 위 그림과 같이 위치할 것이다.

 

 

모든 책을 1로 옮기기 위해서는 첫 걸음 1에 왕복 2를 2회차 만큼 옮기면 된다.

1 + 2 + 2 = 5

 

마찬가지로 모든 책(1은 도착했으므로 제외한다.)을 2로 옮기기 위해서는 첫걸음 1에 왕복 2를 1회차만큼 옮기면 된다.

1+ 2 = 3

 

 

마찬가지로 모든 책(1과 2는 제외)을 3로 옮기기 위해서는 첫걸음 1에 왕복 2를 1회차만큼 옮기면 된다.

1+ 2 = 3

 

 

나머지 4와 5의 경우 한 걸음씩 옮기면 된다.

1 + 1 = 2

 

따라서 5 + 3 + 3 + 2 = 13 이라는 값이 도출된다.

 

도출되는 과정은 입력받은 M을 기준으로 마지막에서 M의 위치까지는 왕복을 할 필요가 없다.

2M의 위치까지는 1번 왕복해야하고,

3M의 위치까지는 2번 왕복을 해야한다.

 

즉, 위의 예제에서는 2개의 책을 들 수 있으므로,

마지막에서 2번째 위치한 4와 5는 왕복을 할 필요가 없고,

마지막에서 4번째 위치한 2와 3은 1번 왕복을 해야한다.

1의 경우는 5번째 위치했기에, 2번 왕복을 했다.

 

 

따라서, 전체 길이인 5까지 이동하는 횟수를 한 번 더해주고, 왕복으로 움직이는 횟수를 더해주면 값이 도출된다.

5 + (2+2)+(2)+(2) = 13

 

 

 

위의 예제에서는 좌표 사이의 거리가 1이기때문에 식을 도출하기 어려울 수 있고, 음수 좌표가 없기 때문에 음수 좌표의 경우도 생각해 주어야 한다.

 

 

 

 

 

 

풀이과정 :

    1. 음수 좌표와 양수 좌표의 책들을 분류한다.

    2. 가장 먼 좌표부터 i 번째까지 위치한 책들은 i / M 만큼 왕복해야한다.

    3.  음수 좌표와 양수 좌표중 작은 값을 먼저 왕복한다.

 

 

 

 

 

 

 

🗝️ 풀이

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

public class baekjoon1461 {

    static int M;
    static List<Integer> leftPosition = new ArrayList<>();
    static List<Integer> rightPosition = new ArrayList<>();

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

        int N = sc.nextInt();
        M = sc.nextInt();

        for (int testCase = 0; testCase < N; testCase++) {
            int position = sc.nextInt();

            if (position < 0) {
                leftPosition.add(Math.abs(position));
            } else {
                rightPosition.add(position);
            }

        }
        leftPosition.add(0);
        rightPosition.add(0);

        solve();
    }

    public static void solve() {

        Collections.sort(leftPosition, Collections.reverseOrder());
        Collections.sort(rightPosition, Collections.reverseOrder());

        int closePosition = leftPosition.get(0);

        if (leftPosition.get(0) > rightPosition.get(0)) {
            closePosition = rightPosition.get(0);
        }

        int sum = closePosition + calMinStep(leftPosition) + calMinStep(rightPosition);
        System.out.println(sum);
    }

    private static int calMinStep(List<Integer> position) {
        int step = position.get(0);

        for (int i = M; i < position.size() - 1; i++) {
            int returnNumber = i / M;
            step += (position.get(i) - position.get(i + 1)) * 2 * returnNumber;
        }
        return step;
    }


}