[백준/Python]1461_도서관

문제

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

1461번: 도서관

풀이

정렬과 그리디 알고리즘을 사용했습니다.

입력으로 주어진 책의 본래 위치를 음수 배열과 양수 배열로 나누고 절댓값의 내림차순으로 정렬합니다.

max_value변수에 절대값이 최대가 되는 값을 저장합니다.(max_value값이 가장 멀기 때문에 세준이의 최종 위치가 됨)

반복문을 통해 왕복해야하는 경우의 수를 walk_cnt 배열에 추가합니다.

최종적으로 walk_cnt안의 항들에 2를 곱하고 max_value값을 합하여 답을 구합니다.

코드

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
books = list(map(int, sys.stdin.readline().rstrip().split()))
left, right = list(), list()
for i in range(len(books)):
    if books[i] > 0:
        right.append(books[i])
        continue
    if books[i] < 0:
        left.append(books[i])
left.sort()
right.sort(reverse=True)

max_value = 0  # 가장 절대값이 큰 값을 저장
for book in books:
    if abs(max_value) < abs(book):
        max_value = book

walk_cnt = []  # 왕복해야되는 경우의 수를 저장
for i in range(0, len(left), m):
    if left[i] != max_value:
        walk_cnt.append(abs(left[i]))
for i in range(0, len(right), m):
    if right[i] != max_value:
        walk_cnt.append(right[i])

answer = abs(max_value)
for cnt in walk_cnt:
    answer += 2 * cnt
print(answer)