📙[Algo] BOJ1461. 도서관

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

문제 요약

• 세준이는 현재 0에 위치
• 책들도 0에 위치
• 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 둘 때 드는 최소 걸음수는?
• 마지막에 0으로 돌아올 필요 X
• 한 번에 최대 M권의 책을 들 수 있음

시간 제한

• 2초

입력

• 책의 개수 N과 한 번에 들 수 있는 책 개수 M
  • N과 M은 50이하 자연수
• 책의 원래 위치가 주어진다.
  • 0인 경우는 없으며, -10000~10000 범위 내 정수

출력

• 다 정리하는 데 필요한 최소 걸음 수 출력

접근법

• 테케1
  • M = 2
  • 책 원래 위치(정렬) : -1 0 3 4 5 6 11
    • 4번, 5번 책 두고 오기 ⇒ 5 + 5 = 10
    • -1번 책 두고 오기 ⇒ 1 + 1 = 2
    • 3번 책 두고 오기 ⇒ 3 + 3 = 6
    • 6번, 11번 책 두기 ⇒ 11
• 테케2
  • M = 2
  • 책 원래 위치(정렬) : -39 -37 -29 -28 -6 0 2 11
    • 2번, 11번 책 두고오기 ⇒ 11 + 11 = 22
    • -6번 책 두고 오기 ⇒ 6 + 6 = 12
    • -29, -28 번 책 두고 오기 ⇒ 29 + 29 = 58
    • -39, -37번 책 두기 ⇒ 39
• 테케3
  • M = 3
  • 책 원래 위치(정렬) : -45 -26 -18 -9 -4 0 22 40 50
    • -9번, -4번 책 두고 오기 ⇒ 9 + 9 = 18
    • -45 , -26, -18번 책 두고 오기 ⇒ 45 + 45 = 90
    • 22, 40, 50번 책 두기 ⇒ 50
• 걸음수는 현재 들고 있는 책의 위치 중 절댓값의 최댓값에 영향 받음
  • 들고있는 나머지 책들은 해당 책을 두러가는 길에 둔다. ⇒ 따라서 음수끼리, 양수끼리 들어야함
• 절댓값이 가장 최대인 책을 포함한 연속된 M권은 가장 마지막에 둘 것
• 나머지는
  • 음수일 경우 가장 왼쪽에서 M개씩 묶어서 이동
  • 양수일 경우 가장 오른쪽에서 M개씩 묶어서 이동
• 이때 양수구간 음수구간을 따로 나눠서 while문을 돌렸다
  • 음수구간
    • start포인터는 절대값이 최대인 값을 가리킨다.
    • start와 end 포인터모두 0부터 시작 → 오른쪽 이동
    • while문 조건 ⇒ end가 N미만 이고, start가 가리키는 원소가 음수인 경우
      • end를 기준으로 M개가 될 때까지 최대한 오른쪽으로 이동
      • start는 M개를 채웠을 때 end 다음 위치로 이동
  • 양수구간
    • end포인터는 절대값이 최대인 값을 가리킨다.
    • start와 end포인터 모두 N-1부터 시작 → 왼쪽 이동
    • while문 조건 ⇒ start가 0이상 이고, end가 가리키는 원소가 양수인 경우
      • start를 기준으로 M개가 될 때까지 최대한 왼쪽으로 이동
      • end는 M개가 채웠을 때 start 이전 위치로 이동

코드

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

public class Main {
    static int N, M;
    static int[] pos;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        pos = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            pos[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(pos);
        int max = Math.max(Math.abs(pos[0]), Math.abs(pos[N - 1])); // 가정 멀리있는 책 위치
        int answer = 0, start = 0, end = 0;
        // 음수 그룹
        while (end < N && pos[start] < 0) {
            // 책 두고 오기
            if (pos[start] < 0 && pos[end] > 0) {
                // 양수인 구간을 만났다면.
                answer += Math.abs(pos[start]) * 2;
                break;
            } else if (end - start + 1 == M) {
                // 개수 최대 M개를 채웠다면 
                answer += Math.abs(pos[start]) * 2;
                start = end + 1;
            } else if (end == N - 1) {
                // 책의 마지막 구간을 만났다면
                answer += Math.abs(pos[start]) * 2;
            }
            end++;
        }

        // 양수 그룹
        start = N - 1; end = N - 1;
        while ( 0 <= start && pos[end] > 0) {
            // 책 두고 오기
            if (pos[end] > 0 && pos[start] < 0) {
                // 음수인 구간을 만났다면
                answer += pos[end] * 2;
                break;
            } else if (end - start + 1 == M) {
                // 개수 최대 M개를 채웠다면
                answer += pos[end] * 2;
                end = start - 1;
            } else if (start == 0) {
                // 책의 마지막 구간을 만났다면
                answer += pos[end] * 2;
            }
            start--;
        }

        System.out.println(answer - max);

    }
}