BOJ #1461

---

LEVEL :

Gold5

---

문제 요약 :

N개의 책을 0에서 시작해 한번에 최대 M개를 가지고 주어진 좌표의 자리에 배치하는데 최소의 움직임을 구하는 문제

---

해결 방안 :

지금까지 greedy를 풀면서 느끼는 것은 정렬의 중요성이다.
현재의 선택에 있어 최선의 선택을 위해서는 정렬 후 최소든 최대든 해당 요구사항에 맞게 풀어나가야 한다는점이다. 이번 문제도 마찬가지였다.
먼저 음수와 양수를 구분하여 정렬한뒤, 가장 먼 거리 방문하여 총 dist 를 구한뒤, dist를 다시한번 오름차순 정렬하여 Pop과정을 거쳐 제일 거리가 먼 곳은 한번만 방문하도록한다.

Solution

import sys
input = sys.stdin.readline
if __name__ == "__main__" :
    k,n = map(int,input().strip().split())
    arr = list(map(int,input().strip().split()))
    arr.sort(reverse= True)
    left = []
    right = []
    for i in range(len(arr)) :
        if arr[i] >=0 :
            left.append(arr[i])
        else :
            right.append(arr[i])
    right = list(map(lambda i: i * -1 , right))
    right.sort(reverse=True)
    dist = []
    
    i=0
    while i < len(left) :
        dist.append(left[i])
        if i+n < len(left) :
            i = i+n
        else: 
            break 
    i=0     
    while i < len(right) :
        dist.append(right[i])
        if i+n < len(right) :
            i = i+n
        else: 
            break
    dist.sort()
    res = dist.pop()
    res += sum(dist)*2
    print(res)