백준 1461 <도서관> Python

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

---

M 권의 책을 한번에 가져올 수 있다는 말은 M 권의 책을 옮기는 과정 중 0 을 지나지 않는다면 먼 거리에 있는 거리 x 2 를 한 것이 해당 과정 중 움직인 거리라는 말이 됩니다.

더불어 0 을 지나게 된다면 책을 들 수 있는 횟수가 초기화되기 때문에 시퀀스의 중단을 의미하기도 합니다. 때문에 0 을 지나지 않고 음수의 인덱스와 양수의 인덱스에 있는 책을 분리해 생각할 수 있습니다.

 

마지막에 있는 책을 옮길 때에는 다시 돌아오지 않아도 되기 때문에 가장 멀리 있는 책을 마지막 에 옮기는 것이 논리적으로 가장 짧게 이동할 수 있는 방법입니다.

즉 마지막에 (가장 멀리있는 책, 가장 멀리있는 책과 같은 부호를 지니며 다음으로 멀리있는 책, ...) 을 옮기는 것이 타당하며 그 다음부터 M 개씩 묶어주면 됩니다.

---

import sys

from collections import deque

from bisect import bisect_right

input = sys.stdin.readline

def solution(N, M, data_list):

    # 이동 거리

    move_length = 0

    # 정렬

    data_list.sort()

    # 가장 멀리있는 인덱스

    far_idx = data_list[0] if abs(data_list[0]) >= abs(data_list[-1]) else data_list[-1]

    # 0 의 위치

    zero_idx = bisect_right(data_list, 0)

    # 0 을 기준으로 두개로 쪼개기 및 데크로 치환

    left_dq = deque(data_list[:zero_idx])

    right_dq = deque(data_list[zero_idx:])

    # 가장 먼 위치에서 M*K 번째 까지 회수

    for i in range(0, len(left_dq), M):

        move_length += -left_dq[i] * 2

    for i in range(len(right_dq)-1, -1, -M):

        move_length += right_dq[i] * 2

    # 가장 멀리있던 인덱스 빼주기

    move_length -= abs(far_idx)

   

    return move_length

# 입력

N, M = map(int, input().strip().split())

data_list = list(map(int, input().strip().split()))

print(solution(N, M, data_list))