[Python] 백준 1461 도서관

문제 링크 : https://www.acmicpc.net/problem/1461

1461번: 도서관

1. 접근 방법

마지막 책을 옮긴 후 다시 원점으로 돌아올 필요가 없어서 가장 멀리 있는 위치를 마지막에 가는 것은 어렵기 않게 생각했는데, 세부적 구현에서 많이 고민했다.

최적의 위치를 잘 찾는것이 이 문제의 가장 중요한 부분이라 생각한다.

 

 

2. 풀이 코드

🖥python 코드

import sys
input = sys.stdin.readline
MIIS = lambda: map(int, input().split())


n, m = MIIS()
books = MIIS()

# 양수 좌표, 음수 좌표로 나누가
positives = []
negatives = []
for book in books:
    if book > 0:
        positives.append(book)
    else:
        negatives.append(abs(book))

positives.sort(reverse=True)
negatives.sort(reverse=True)

positive_times = positives[::m]
negative_times = negatives[::m]


# 조건별로 처리 >> 출력
if not positive_times:
    print(sum(negative_times) * 2 - negative_times[0])
elif not negative_times:
    print(sum(positive_times) * 2 - positive_times[0])
elif positive_times[0] >= negative_times[0]:
    print((sum(positive_times) + sum(negative_times)) * 2 - positive_times[0])
elif positive_times[0] < negative_times[0]:
    print((sum(positive_times) + sum(negative_times)) * 2 - negative_times[0])

📕풀이 방법

1. 이동을 최소로 하기 위해 가장 먼저 양수, 음수 좌표끼리 구분한다. 한 번에 책을 여러 권 든다고 해도 양수, 음수 좌표를 동시에 가면 최적의 시간을 구하지 못할 수도 있다.

2. 각 음수, 양수 좌표에서, 가장 멀리 있는 위치에서 시작해서 m개 마다 위치를 가져온다.

    이 부분을 떠올리기 쉽지 않았는데, 가장 먼 위치를 기준으로 한다면, 그보다 앞에 있는 위치는 가는 길에 무조건 들렀다 갈 수 있기 때문에 가장 먼 위치부터 하는 방법이 옳다

3. 양수, 음수 좌표에서 모두 계산을 하고나서, 가장 멀리 있는 위치는 편도만 가도록 하고, 나머지 위치는 왕복으로 길이를 계산하여 출력한다.

 

 

3. 생각 정리

인덱스를 잘 끊어서 해결하는 부분이 많이 햇갈렸다.

처음 시도는 while문으로 했는데, 예를 들어 m=3이면 1개를 뽑아 길이 계산으로 사용하고, 나머지 2개는 그냥 pop을 하거나 인덱스만 더해서 넘어가도록 했다.

그다음에는 for문 range에서 범위를 설정하려 했는데, 결과적으로 리스트 슬라이싱과 같은 방식이라서 슬라이싱으로 문제를 해결했다.