https://www.acmicpc.net/problem/1461
1461번: 도서관
세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책
www.acmicpc.net
백준 - 도서관 (1461번)
난이도 : Gold 5
알고리즘 : Sorting (정렬)
풀이 소요 시간 : 25 mins
Time Complexity : O( N * logN )
if __name__ == '__main__':
N, M = map(int, input().split())
pos = list(map(int, input().split()))
neg = sorted([i for i in pos if i < 0])
pos = sorted([i for i in pos if i > 0], reverse=True)
neg.append(0)
pos.append(0)
foot = sum(pos[i] for i in range(0, len(pos), M)) - sum(neg[i] for i in range(0, len(neg), M))
foot <<= 1
foot -= pos[0] if -neg[0] <= pos[0] else -neg[0]
print(foot)
양수와 음수를 분리해서, 각각 정렬한다.
한 번에 M개의 책을 옮길 수 있으므로,
양수와 음수 각각의 리스트에서
절댓값이 가장 큰 수부터 M개씩 건너 뛰어가며
총 합 foot을 구한다.
책으로 갔다가 다시 0으로 돌아와야 하기 때문에,
foot에 2를 곱해준다.
그리고 마지막 위치가 0일 필요는 없으므로,
양수와 음수 리스트 중 절대값이 가장 큰 값을
foot에서 빼준다.
그러면 현재 상태의 foot이 최소 걸음 수가 된다.
예제 입력 2 예시
8 3
-18 -9 -4 50 22 -26 40 -45
에서
pos = [ 50 40 22 ]
neg = [ -45 -26 -18 -9 -4 ]
이다.
M = 3 개씩 건너뛰면
pos = [ 50 40 22 ]
neg = [ -45 -26 -18 -9 -4 ]
이고,
색칠된 값들을 모두 더하고 2를 곱하면
foot = ( 50 + | -45 | + | -9 | ) * 2 = 208
이 된다.
그리고 pos와 neg 중 절댓값이 가장 큰 수를 빼주면
foot = foot - 50 = 158
이 된다.
'Algorithm' 카테고리의 다른 글
파티 (1238번) - 백준 (BOJ) (0) | 2023.06.08 |
---|---|
과제 진행하기 (176962번) - 프로그래머스 (Programmers) (0) | 2023.06.07 |
치즈 (2638번) - 백준 (BOJ) (0) | 2023.06.05 |
ACM Craft (1005번) - 백준 (BOJ) (0) | 2023.06.05 |
교환 (1039번) - 백준 (BOJ) (0) | 2023.06.03 |