백준 1461. 도서관

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

1461번: 도서관

 

코드

n, m = map(int, input().split())
location = list(map(int, input().split()))

minus = []
plus = []
ans = 0
for i in range(n):
    if location[i] < 0:
        minus.append(location[i])
    else:
        plus.append(location[i])

minus.sort(reverse = True)  # 음수는 내림차순 정렬 (절댓값(거리)이 큰 게 뒤로 가게 정렬)
plus.sort()  # 양수는 오름차순 정렬

# 가장 큰 수 구하기
if len(minus) == 0:
    max_num = max(plus)
elif len(plus) == 0:
    max_num = -min(minus)
else:
    max_num = max(max(plus), -min(minus))

while minus:
    for i in range(m):
        if len(minus) == 0:
            break
        if i == 0:
            ans -= minus.pop() * 2
        else:
            minus.pop()

while plus:
    for i in range(m):
        if len(plus) == 0:
            break
        if i == 0:
            ans += plus.pop() * 2
        else:
            plus.pop()

print(ans - max_num)

 

입력으로 들어오는 책의 위치 값들을

양수와 음수 리스트로 나누어 저장한다.

 

음수는 절댓값, 즉 거리가 큰 것이 뒤로 가게 내림차순 정렬을 하고

양수는 오름차순 정렬을 해준다. 

 

양수 리스트와 음수 리스트를 통틀어서

가장 큰 값을 max_num 변수에 넣어준다.

 

한 번 이동할 때, m 개의 책을 가지고 이동할 수 있고

위치가 먼 책을 가져다 두면서,

해당 위치보다 작은 위치의 책도 같이 들고 가면

최소 걸음으로 책을 정리할 수 있기 때문에

 

m만큼 반복문을 돌며

끝 값을 삭제해서 2배 해주고(가는 거리 + 오는 거리)

 

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

가장 큰 값은 마지막에 정리해줌으로써

최소값을 만들어 준다.

 

m 반복문을 돌 때

가장 큰 값을 마지막에 정리하는 것을 고려하지 않고

책을 정리했기 때문에

정답값에서 처음에 구한 가장 큰 값인 max_num을 한 번 빼준다.