1461

날짜 : 2022. 12. 01

사용 언어 : python

 

문제

 

 

코드

import sys
n, m = map(int, sys.stdin.readline().split())
book = list(map(int, sys.stdin.readline().split()))
po = [] # 양수
ne = [] # 음수
dist = []
for i in book:
    if i > 0: po.append(i)
    else: ne.append(i)
        
po.sort(reverse = True)  # 내림차순
ne.sort()  # 오름차순(절댓값 순서)

for i in range(0, len(po), m): dist.append(po[i])
for i in range(0, len(ne), m): dist.append(abs(ne[i]))

dist.sort()
res = 0
for i in range(len(dist)-1):
    res += (dist[i] * 2)
res += dist[-1]
print(res)

 

 

풀이

- 케이스를 기준으로 생각하면 다음과 같다.

예제 1에서는 m = 2 개의 가방을 집을 수 있고 수열은 -37 2 -6 -39 -29 11 -28 이다.

이를 양수와 음수를 구분하여 정렬 후 양수는 내림차순, 음수는 오름차순으로 정렬한다.

(절댓값이 큰 곳으로 이동하면서 전달한다는 개념으로 생각하면 된다.)

양수 : 11 2

음수 : -39 -37 -29 -28 -6

총 2개씩 옮길 수 있으니까 (11, 2) (-39, -37) (-29, -28) (-6)으로 묶을 수 있고 0에서부터 출발하기 때문에 편도 거리가 가장 긴 경우는 가장 마지막으로 배치함으로써 왕복으로 움직이지 않게 해야 한다.

그 결과 (-39, -37)을 가장 마지막으로 배치하여 39만큼만 이동한다.

그렇다면 11*2 + 29*2 + 6*2 + 39 = 131이 도출된다.

 

 

알게된 점

- 예제에서 131이 도출되는 과정을 곧바로 파악하진 못했다. 단순히 음수 -> 양수 순서로 전개해서 (-39, -37)이 편도라는 것을 간과했다.

 

 

참고 사이트

-