문제 설명
•
: 책의 개수
•
: 한 번에 들고 갈 수 있는 책의 개수
•
책 개의 좌표가 주어질 때, 책을 모두 제자리에 놓는 데 걸리는 최소 시간을 구하는 문제
예제 입력/출력
•
입력1
7 2
-37 2 -6 -39 -29 11 -28
Plain Text
복사
•
출력1
131
Plain Text
복사
•
입력2
8 3
-18 -9 -4 50 22 -26 40 -45
Plain Text
복사
•
출력2
158
Plain Text
복사
•
입력3
6 2
3 4 5 6 11 -1
Plain Text
복사
•
출력3
29
Plain Text
복사
•
입력4
1 50
1
Plain Text
복사
•
출력4
1
Plain Text
복사
제약 조건
•
•
책의 위치는 0이 아니며, 절대값은 10,000 이하
문제 풀이
•
모든 경우를 살펴보는 브루트 포스적인 풀이는 힘든 구조의 문제이다.
상한
•
아래와 같은 그리디한 아이디어를 통하여 문제를 해결할 수 있다.
1.
출발할 때, 책은 무조건 권을 드는 게 이득이다.
2.
출발한 이후에 방향 전환을 하지 않는 게 이득이다.
•
정확히는 양수로 간다면 양수로만, 음수로 간다면 음수로만 이동
3.
먼 곳에 있는 곳부터 가는 게 이득
•
(가까운 곳부터 가는 경우) 5 + 9 + 13 = 27
•
(먼 곳부터 가는 경우) 2 + 7 + 13 = 22
→ 먼 곳을 먼저 가는 게 이득
•
모든 방문 점들의 합을 구한 다음 2를 곱해주고, 가장 큰 값을 빼준다.
◦
2를 곱해주는 이유 = 원점으로 가서 책을 다시 들고오기 위해서
◦
가장 큰 값을 빼주는 이유 = 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요가 없기 때문이다.
ans = 2 * sum(dists) - max(dists)
Python
복사
풀이 코드
내가 푼 코드
N, M = map(int, input().split())
arr = list(map(int, input().split()))
neg = []
pos = []
for x in arr:
if x > 0:
pos.append(x)
else:
neg.append(-x)
pos = sorted(pos)[::-1]
neg = sorted(neg)[::-1]
dists = []
for p in pos[::M]:
dists.append(p)
for n in neg[::M]:
dists.append(n)
ans = 2 * sum(dists) - max(dists)
print(ans)
Python
복사
알아두면 좋은 내용들
파이썬의 슬라이싱 완벽히 이해하기