[백준] 1461번 도서관, 파이썬 문제풀이

문제

백준 1461번 최소한의 걸음으로 책을 되돌려놓는 문제를 해결했습니다.

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

1461번: 도서관

문제

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

입력

첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 책의 위치는 0이 아니며, 절댓값은 10,000보다 작거나 같은 정수이다.

예시: 7 2

       -37 2 -6 -39 -29 11 -28

출력

첫째 줄에 정답을 출력한다.

예시: 131

 

문제 풀이

책의 개수와 한 번에 들 수 있는 책의 수, 책의 위치가 주어지면, 최소한의 걸음으로 책을 되돌려놓는 문제입니다. 마지막 책을 가져다놓고 다시 원점으로 돌아올 필요가 없습니다. 때문에, 가장 멀리 있는 책을 마지막에 가져다 놓는 것이 포인트입니다. 또한, 책의 좌표는 양수, 음수가 섞여있습니다. 부호가 다른 책을 동시에 가져다 놓을 이유는 없습니다. 원점을 지나쳐가기 때문에, 차라리 놓고 가면 다른 책을 함께 가져다 놓을

수 있기 때문입니다.

 

문제를 해결하기 위해, 그리디 알고리즘(탐욕 알고리즘)을 활용했습니다. 절대값이 큰 순서대로 정렬해 멀리 있는 책부터 가져다 놓는 것입니다. 양수와 음수에 있는 책들은 한 번에 가져갈 필요가 없기 때문에, 우선 둘이 분리해 따로 계산합니다. 양, 음수에 있는 책 중 가장 멀리 있는 책을 나중에 가져다 놓는 걸로 하고, 각각 묶어서 계산하는 것입니다. 

 

주어진 예시를 보면, 7권의 책을 2권씩 들고갈 수 있습니다. 책의 위치를 부호에 따라 나눠 절대값이 큰 순서대로 정렬하면 다음과 같습니다.

 

양수: 11, 2

음수: -39, -37, -29, -28, -6

 

음수에 있는 책이 가장 멀리 있기 때문에, 마지막에 가져다 놓습니다. 그 외에 다른 책을 두 권씩 묶어서 가져다 놓으면 다음과 같습니다.

 

2, 11 위치의 책을 한 번에 가져다 놓는다. → 사용한 걸음 수 : 22 / 합계: 22

-6 위치의 책을 가져다 놓는다. → 사용한 걸음 수 : 12 / 합계: 34

-28, -29 위치의 책을 한 번에 가져다 놓는다. → 사용한 걸음 수 : 58 / 합계 : 92

-37, -39 위치의 책을 한 번에 가져다 놓고 마친다. → 사용한 걸음 수 : 39 / 합계 : 131

 

왜 -6위치의 책은 혼자 가져다 놨을까요? 2권씩 묶어서 가져다 놓는다는 논리대로라면, -6, -28이 한 번에 가야합니다. 머릿속으로는 아닌걸 알아도, 프로그램 상 그래야합니다. 우리는 최소한의 거리를 알기 위해서는 반대로 생각을 해야합니다. 위에서 말한 순서의 반대로 진행하면 2권씩 묶었을 때, -6 위치의 책만 남은 것을 알 수 있습니다.

 

정리하면, 가장 멀리 있는 책은 거리X2를 하지 않고, 거리가 먼 책부터 2권씩 묶는다. 음수와 양수 중, 더 멀리있는 책을 마지막에 가져다 놓는다.

 

이렇게, 절대값이 큰 책부터 가져다 놓는 것이 그리디 알고리즘입니다. 현재 할 수 있는 것중 최선의 선택, 즉 가장 멀리 있는 책을 가져다 놓는것입니다. 이를 코드로 표현하면 다음과 같습니다.

N, M = map(int, input().split())
d = list(map(int,input().split()))

result=0
positive = []
negative = []

for i in d:
    if(i>0):
        positive.append(i)
    else:
        negative.append(i)

positive.sort(reverse=True) // 절대값 기준 내림차순 정렬
negative.sort()


if(len(negative)==0): // 음수에 있는 책이 없으면 양수에 있는 책을 마지막에 넣음
    result+=positive[0]
elif(len(positive)==0): // 양수도 마찬가지
    result+=abs(negative[0])
elif(abs(negative[0]) < abs(positive[0])): // 절대값이 큰 책을 마지막에 넣음
    result+=positive[0]
    result+=abs(negative[0])*2 // 마지막이 아니기 때문에 돌아오는 거리 계산
else:
    result+=positive[0]*2
    result+=abs(negative[0]) // 음수이기 때문에 절대값을 더하기 위해 abs 함수 사용

i=1
idx=1
while(len(positive)!=1 and i*M < len(positive)): // 양수에 있는 책부터 계산
    idx=i*M // 들 수 있는 것 중 가장 큰 것만 고르기 위해
    if(idx>len(positive)): // 인덱스가 넘어가면 마지막에 있는 것 계산
        result += positive[-1]*2
    else:
        result += positive[idx]*2
    i+=1
i=1
idx=1
while(len(negative)!=1 and i*M < len(negative)): // 음수도 마찬가지
    idx=i*M
    if(idx>len(negative)):
        result += abs(negative[-1])*2
    else:
        result += abs(negative[idx])*2
    i+=1

print(result)

정리

그리디 알고리즘을 활용한 문제를 해결하고 있습니다. 이 과정에서 우선순위 큐가 사용되는 경우가 많은 것 같아 따로 공부한 뒤 포스팅할 예정입니다.