[baekjoon] 백준 1461번(파이썬): 도서관

문제

1461번: 도서관

- 세준이는 도서관에서 일한다.

- 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다.

- 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다.

- 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 구하는 문제이다.

- 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다.

- 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다.

- 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

- 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다.

- N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다.

- 책의 위치가 주어진다 책의 위치는 0이 아니며, 그 절댓값이 10,000보다 작거나 같다.

알고리즘

- 책의 개수와 한 번에 들 수 있는 책의 개수를 입력받는다.

- 책의 제자리 위치를 입력받아 리스트 변수에 넣는다.

- 책의 제자리 위치는 양수 음수로 되어있으므로 양수 음수로 나누어 계산한다.

- 책을 모두 제자리에 놔둔 후에는 원래 자리인 0으로 돌아올 필요가 없기 때문에 제일 멀리 있는 책을 제일 마지막에 놔둔다. 

- 책을 갔다 두면서 그보다 가까운 책을 같이 가져가 책을 놔둘 수 있으므로 양수는 내림차순, 음수는 오름차순으로 정렬한다.

- 반복문을 통해 양수 방향에 책과 음수 방향에 책을 m권씩 확인하여 최소 걸음 수에 더한다.

- 최소 걸음 수는 왕복해야 하기 때문에 곱하기 2를 하고 제일 멀리 있는 책의 위치를 더한다. 

코드

import sys

n, m = map(int, sys.stdin.readline().split())
walk = list(map(int, sys.stdin.readline().split()))
plus_walk = []
minus_walk = []
max_walk = 0 # 제일 멀리 있는 책의 위치

for i in walk:
    # 양수와 음수를 나눈다.
    if i > 0:
        plus_walk.append(i)
    else:
        minus_walk.append(i)

    # 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요 없기때문에
    # 마지막 책은 제일 멀리 있는 책으로 정한다.
    if abs(i) > abs(max_walk):
        max_walk = i

# 양수는 내림차순으로 음수는 오름차순으로 정렬한다.
plus_walk.sort(reverse= True)
minus_walk.sort()

# 최소 걸음 수
walking = 0

# m권을 들고 양수 방향에 책을 모두 제자리에 놔둔다.
for j in range(0, len(plus_walk), m):
    # 제일 멀리 있는 책은 무시한다.
    if plus_walk[j] != max_walk:
        walking += plus_walk[j]

# m권을 들고 음수 방향에 책을 모두 제자리에 놔둔다.
for k in range(0, len(minus_walk), m):
    # 제일 멀리 있는 책은 무시한다.
    if minus_walk[k] != max_walk:
        # 최소 걸음 수를 계산하기 위해 절대값으로 바꿔 더한다.
        walking += abs(minus_walk[k])
        
# 최소 걸음 수는 책의 제자리 위치와 현재 책의 위치를 왕복하여 계산한다.
walking *= 2
# 제일 멀리 있는 책을 놔둔다.
walking += abs(max_walk)

print(walking)

결과

위 코드에서 반복문을 확인해보면 m권씩 증가시켜 각 리스트를 반복한다. m권씩 증가시켜 확인하는 이유는 양수 방향에 있는 책은 내림차순, 음수 방향에 있는 책은 오름차순으로 정렬했기 때문에 m권씩 들고 갈 때, 제일 첫 번째 책을 놔두면서 그전에 있는 책을 모두 놔둘 수 있게 되기 때문이다. 따라서 m권씩 들고 갈 때에 첫 번째 책을 최소 걸음수에 더하는 것을 확인할 수 있다. 최소 걸음수는 모두 양수로 받아 더하고 책을 놔둘 때 왕복을 하기 때문에 곱하기 2를 해주는 것을 알 수 있다. 마지막으로는 제일 멀리 있는 책을 더하여 최소 걸음수를 구할 수 있게 된다.

github

junjange/CodingTest