[백준] #1461 도서관(python)

📌문제

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

입력

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

출력

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

예제 입력1

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

예제 출력1

131

예제 입력2

8 3
-18 -9 -4 50 22 -26 40 -45

예제 출력2

158

예제 입력3

6 2
3 4 5 6 11 -1

예제 출력3

29

예제 입력4

1 50
1

예제 출력4

1

백준 1461번 문제

💡Idea

예제 1의 책📚들의 좌표를 나타내보면 다음과 같습니다.

세준이가 한 번에 들 수 있는 책은 2권이기 때문에, 0 좌표로부터 멀리 떨어져 있는 좌표들은 한 번에 두 개씩 차례대로 책을 가져다 놓을 수 있습니다.

먼저 0보다 큰 좌표를 가진 책들은 아래와 같이 가져다 놓을 수 있습니다.

좌표 2와 좌표 11의 책을 함께 들고 이동하여 한 번에 두 권의 책을 가져다 놓을 수 있습니다.

또한, 0보다 작은 좌표를 가진 책들도 아래와 같이 한 번에 두 권씩 가져다 놓을 수 있습니다.

-6은 한 권만 들고 가져다 놓고, -29와 -28, -39와 -37을 한 번에 가져다 놓으면 됩니다.

이 때, 마지막으로 가져다 놓은 -39의 경우 다시 좌표 0으로 돌아오지 않아도 됩니다.

최소 걸음 수가 되려면, 이렇게 멀리 있는 좌표들은 한 번에 최대한 많이 처리하고, 0에서 가장 멀리 떨어져 있는 책을 마지막에 가져다 놓아야 합니다.

따라서, 이 문제는 아래와 같은 방식으로 해결할 수 있습니다.

1. 좌표가 양수인 책들과 음수인 책들을 따로 관리한다.
2. 각각에 대하여 좌표 0과 멀리 떨어져 있는 책들부터, 최대로 들 수 있는 책만큼씩 가져다 놓는다.
3. 마지막으로 가져다 놓는 책의 경우 다시 0으로 돌아오지 않아도 되기 때문에, 양수와 음수 상관없이 가장 먼 거리에 있는 책을 가장 마지막 순서로 하여 해당 거리를 빼준다.

💻코드

• ⏰ 시간 : 36 ms / 메모리 : 30616 KB

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
books = sorted(list(map(int, input().split())))
ans = 0

books_pos = [b for b in books if b > 0]
books_neg = [b for b in books if b < 0]

for i in range(len(books_pos)-1, -1, -M): # 마지막 인덱스가 0으로부터 가장 먼 좌표
    ans += (books_pos[i] * 2)

for i in range(0, len(books_neg), M): # 첫 인덱스가 0으로부터 가장 먼 좌표
    ans += (-books_neg[i] * 2)

value = max(books_pos[-1] if books_pos else 0, -books_neg[0] if books_neg else 0)
print(ans - value)

📝코드 설명

변수

• books_pos : 입력 받은 책들의 좌표 중 양수 좌표
• books_neg : 입력 받은 책들의 좌표 중 음수 좌표

먼저 입력받은 책들을 정렬해줍니다.

그런 뒤, 양수 좌표의 책들 먼저 책을 가져다 놓습니다.
가장 멀리 떨어져 있는 책들을 한꺼번에 가져다 놓을 수 있도록, 가장 멀리 있는 좌표부터 M(최대로 들 수 있는 책의 개수)만큼 건너뛰며 ans에 더해줍니다.

그리고 음수 좌표의 책들을 가져다 놓습니다.
양수 좌표의 과정과 동일하게 가장 멀리 떨어져 있는 좌표부터 M씩 건너뛰며 더해줍니다.

둘 다 더해줄 때는 다시 0으로 돌아오는 것도 함께 생각하여 2배 해준 값을 더해줘야 합니다.

그리고, 가장 먼 좌표를 0으로 돌아오지 않아도 되는 마지막 순서로 해야 합니다.
따라서, 더해준 값에서 가장 먼 좌표 값을 빼주면 됩니다.