[백준] 1461 파이썬

문제

---

• 백준 1461 (골드 4)

백준 1461

원점에 위치한 n개의 책들을 원래 위치로 돌려놓기 위한 최소 거리를 구하는 문제였다.
이때 문제의 조건이 한번에 m개의 책만 들 수 있다는 것이였다.
시간제한 2초에 n과 m이 각각 50보다 작은 자연수라는 점에서 시간 제한은 널널한 문제였다.

내 코드

---

어제 풀었던 투포인터 관련 문제인가 싶어서 10분정도 알고리즘을 고민하였다.
차근차근 생각해보니 알고리즘 없이 단순 구현으로 풀 수 있는 문제 같았다.
우선 책의 위치를 양수와 음수로 구분하여 각각 리스트에 담고, 절대값을 기준으로 내림차순 정렬하였다.
이때, 음수 위치 리스트는 양수로 변환하여 다루기 쉽게 만들었다.
각 리스트에서 거리가 먼 책부터 m 권씩 건너뛰며 왕복 거리를 결과에 더해주었다.
책을 가져온 후 다시 원점으로 돌아가야 하기 때문에 2를 곱하여 왕복 거리를 더해주었다.
마지막에는 다시 원점으로 돌아갈 필요가 없기 때문에 전체 위치 절대값이 가장 큰 값을 빼주었다.

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
books = list(map(int,input().split()))
books_p = []
books_m = []

for book in books:
    if book > 0:
        books_p.append(book)
    else:
        books_m.append(-book)

books_m.sort(reverse=True)
books_p.sort(reverse=True)

def sum(book_list):
    index = 0
    ans = 0
    while index < len(book_list):
        ans += 2 * book_list[index]
        index += m
    return ans

if len(books_p) == 0 and len(books_m) == 0:
    print(0)
elif len(books_p) == 0:
    print(sum(books_m) - max(books_m))
elif len(books_m) == 0:
    print(sum(books_p) - max(books_p))
else:
    print(sum(books_m) + sum(books_p) - max(max(books_m), max(books_p)))

문제를 억지로 알고리즘에 대입하려하기보단 차근차근 문제의 조건들을 따라가면서 고민해보면 자연스럽게 풀 수 있다는 것을 알게 되었다.