백준 & 프로그래머스
[백준] 1461번: 도서관 - python
hyukji
2023. 1. 10. 21:04
문제보기
https://www.acmicpc.net/problem/1461
1461번: 도서관
세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책
www.acmicpc.net
풀이 및 코드
해당 문제는 Greedy문제로 solved.ac에 골드 5로 랭크되어 있다.
풀이법은 가장 먼 곳부터 생각하고 코드를 작성하면 편하다!(물론 실제로는 가장 먼 곳을 마지막에 가야 한다) 즉 가장 먼 곳으로 가되 그 다음으로 먼 책 m개를 챙겨서 가져간다고 생각하면 된다. 주의할 점은 실제로 가장 먼 곳은 갔다가 돌아오지 않앙 하기에 거리 * 2가 아닌 그냥 거리만 더해주면 된다. 또한 양수와 음수는 따로 계산한다. 이유는 양수 a와 음수 b를 같이 운반하고 0으로 돌아오면 이동 거리는 a+a + b+b가 된다. 이는 음수 양수 따로 운반한 a+a, b+b의 합과 같다!
필자가 처음 코드를 짤 때에는 다음의 로직을 따라 작성했다.
- input list를 정렬한 후에 음수, 양수로 나누어 0부터의 거리를 배열로 저장한다.
- 거리가 가장 먼 위치를 찾아 answer에 더해주고, 해당 배열에서 m개를 제거한다.
- 각각의 배열의 가장 큰 값 * 2를 answer에 더해주고, 해당 배열의 길이가 0이 될 때까지 m개를 제거한다
그런데 다른 분들의 코드를 보면서 더 좋은 코드가 있음을 알았다. 바로 해당 메서드를 이용한 코드이다.
arr = [1,2,3,4,5,6,7]
print(arr[::3])
# [1,4,7]
arr[a:b:c] 는 index a부터 index b까지 c개 단위로 꺼낸 list이다. 해당 메서드를 이용하면 다음과 같이 비교적 깔끔하게 코드를 짤 수 있다!
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys | |
input = sys.stdin.readline | |
n, m = map(int, input().split()) | |
loc = sorted(list(map(int, input().split()))) | |
postive = [] | |
negative = [] | |
for l in loc: | |
if l < 0: | |
negative.append(-l) | |
else: | |
postive.append(l) | |
postive.reverse() | |
print((sum(negative[::m]) + sum(postive[::m])) * 2 - max(negative + postive)) |