📚 1461 - 도서관

도서관

이해

문제 규칙을 보면 쉽게 문제를 풀 수 있을 것이다.

✔️ 문제 규칙(힌트)
0을 기준으로 음수 또는 양수 위치로 이동을 해야한다.
세준이는 최소 걸음 수를 원한다.

• 음수쪽에서 양수쪽으로 다시 돌아오려면, 더 많은 걸음 수가 필요하다.
• 둘 중 한쪽을 끝내고 다른 쪽에서 책을 다시 가져다 놓으면 된다.

책 같은 경우도 한 번에 들 수 있는 책의 개수 만큼 들어서 가장 먼 곳부터 시작하여 가는 길에 책을 제자리에 놔두면 된다.

• 마지막으로 책을 제자리에 놔두었다면 다시 0으로 돌아올 필요가 없다.
• 그러면 가장 먼 곳에 있는 책을 가장 마지막에 제자리에 두면 되는 것을 알 수 있다.

✔️ 문제 풀이
이와 같은 문제를 풀 때는 음수 구간, 양수 구간을 따로 준다면 쉽게 풀 수 있다.

8 3
-18 -9 -4 50 22 -26 40 -45

일 때

음수 : -45 -26 -18 -9 -4
양수 : 22 40 50

음수 배열 인덱스마다 -1을 주어 실제 거리를 구한다.

• 0에서 시작하여 음수, 양수 지역을 모두 방문해야 한다.
• 한 번에 들 수 있는 책의 개수가 3이다.

4 9 18 26 45 일 때

45 26 18 : 거리 45 x 2 (o)
9 4 : 거리 9 x 2 (o)

45 26 : 거리 45 x 2
18 9 4 : 거리 18 x 2


22 40 50 일 때
50 40 20 : 거리 50 (마지막에 제자리에 책을 두었기에 돌아올 필요가 없다.)

이와 같이 내림차순으로 한 번에 들 수 있는 책의 개수 만큼 들어서 제자리에 놔두면 된다.

추가로, '책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다.' 라고 하였기에 50을 가장 마지막에 제자리 책을 두면 된다.

소스

import sys

read = sys.stdin.readline

n, m = map(int, read().split())

books = list(map(int, read().split()))

minus_arr = [0]
plus_arr = [0]
answer = 0

# 음수, 양수 부분 나누기
for book_loc in books:
    if book_loc < 0:
        minus_arr.append(book_loc * -1)
    else:
        plus_arr.append(book_loc)

minus_arr.sort(reverse=True)
plus_arr.sort(reverse=True)

for i in range(0, len(minus_arr), m):
    answer += (minus_arr[i] * 2)

for i in range(0, len(plus_arr), m):
    answer += (plus_arr[i] * 2)

answer -= max(max(minus_arr), max(plus_arr)) # 마지막에 제자리에 둔 책 거리를 빼준다.

print(answer)