[백준] 1461 - 도서관 📚 (Python) / 골드 5 / 그리디

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

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

문제 설명

요약하자면, 일직선 좌표가 있고, 0 위치에 어질러진 책들을 각각 원래 자리에 가져다 둬야 하는데 최소한으로 움직여야 하고, 최소한의 거리를 출력하는 문제입니다.

주의할 점은 책의 위치는 0이 아니라는 것과 마지막 책을 가져다 두고는 0으로 다시 돌아올 필요가 없다는 점입니다.

1) 예제 입출력❄️

예제 입출력

첫 번째 예제를 보면, 7권을 갔다 놔야 하고, 한 번에 들 수 있는 책은 최대 2권입니다.

다음 줄에 7권에 대해 원래 자리의 좌표가 공백을 구분자로 입력됩니다.

2. 핵심 논리☢️

핵심은 양수와 음수를 나눠서 리스트에 저장하고, M권씩 묶어서 가져다 두는데, 먼 위치부터 가져다 둬야 한다는 점과 전체 책 위치 중 가장 먼 위치에 가져다 두고는 0으로 돌아오지 않아도 된다는 것입니다.

3. 풀이 코드✅

N,M=[*map(int,input().split())]
books=[*map(int,input().split())]

positive_li = []; negative_li = []; last = 0
for b in books:
    last = max(abs(b),last)
    if b>0:
        positive_li.append(b)
    else:
        negative_li.append(abs(b))
positive_li.sort(reverse = 1); negative_li.sort(reverse = 1)

result = 0
for i in range(0, len(positive_li), M):
    result += positive_li[i]*2
for i in range(0, len(negative_li), M):
    result += negative_li[i]*2
print(result-last)

N(전체 책 권수), M(한 번에 들 수 있는 최대 책 권수), books(책의 위치 리스트)를 입력받습니다.

books를 반복하며 0보다 크면 positive_li에 넣고, 그 외에는 절댓값을 취해서 negative_li에 넣습니다. (책의 위치로 0은 주어지지 않는다고 했습니다.) 그리고 last변수에는 책 위치 중 가장 먼 거리를 저장합니다.

다음에 positive_li와 negative_li를 내림차순으로 정렬합니다. 그 이유는 가장 먼 곳부터 M 권씩 반납해야 최소 걸음을 보장하기 때문입니다. 이걸 증명하는 건 글이 길어지니 가장 간단하게 책이 1, 6, 7이고 M=2 일 때 6, 7을 한 번에 반납하는 게 제일 이득이고 다른 경우에도 모두 성립됩니다.

negative_li에 절댓값으로 저장한 이유는 어차피 거리를 재야 하기 때문에 양수로 저장한 것입니다. 즉, 2개의 양수 리스트에 책을 가져다 두는 문제로 바꿨습니다. 이제 result 변수에 전체 왔다갔다한 거리를 저장할 것이니 0으로 초기화합니다.

positive_li와 negative_li에 대해서 0부터 M개씩 건너 뛰어가며 2를 곱해 result에 저장합니다. 이 의미는 한 번에 반납할 M권의 책 중에 가장 먼 위치만 저장하는 것입니다. 예를 들어 M이 2이고, 1과 3 좌표의 책을 반납한다면 3까지만 갔다가 0으로 온 거리만 저장하면 되기 때문입니다. 

그리고 마지막에 result에서 last를 빼주는데 마지막 제일 먼 위치의 책을 반납하고는 0으로 돌아오지 않아도 되기 때문입니다.

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/9450e25b69c05e09ada058d364a36f4f17996659/jupyter/1461_%EB%8F%84%EC%84%9C%EA%B4%80.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/