경이로운 그리디 알고리즘3 -가장 효율적으로 좌우로 이동하는 방법-

1. 문제

 

1461번: 도서관 (acmicpc.net)

1461번: 도서관

 

2. 풀이

 

문제를 좀 파악부터 해보면

 

배열의 원소가 책의 위치이며

 

0에서 시작해서 이동을 해가지고 m개 이내의 책을 들고 다시 0으로 돌아와서 책을 둔 다음에,

 

이런 식으로 모든 책을 회수해야할때, 최소 이동거리를 구해라

 

마지막에 모든 책을 회수할때는 0으로 돌아오지 않아도 된다

 

---------------------------------------------------------------------------------------------------

 

1) 그러면 돌아오지 않아도 되는 마지막에는 가장 먼 지점으로 이동하는게 이득이다.

 

그러니까 배열을 일단 정렬하는게 맞겠지

 

2) 당연하지만 왔다갔다해야하니까, 최대한 m개의 책을 모두 가지고 돌아가는게 무조건 이득이겠지

 

m개의 책을 들었으면 더 이상 책을 들 수 없으니까 0으로 이동해야하는데,

 

양수 방향으로 갔다가 책을 조금 들고 음수 방향으로 갔다가 나머지 책을 들고 다시 0으로 돌아오면 당연히 손해보겠지

 

3) 왔다갔다는 단 1번만 하는게 무조건 이득이다

 

그러니까 애초에 한방향으로만 이동해서 0으로 돌아오는게 이득

 

 

 

4) 0에서 이동을 시작할때 최대한 멀리까지 이동하고, 이동하면서 보이는 책은 다 들고 

 

책을 다 들었으면 돌아오면 되겠지

 

위 그림처럼 3,8 위치에 책이 있고 2권까지 들 수 있으면 8까지 이동하고 이동하면서 3에 있는 책은 자연스럽게 들고 간다면

 

8까지만 이동하는 것으로 3에 있는 책을 들 수 있는 이득을 보는거니까

 

-----------------------------------------------------------------------------------------------------------------------------------------

 

근데 이제 이렇게 생각하는게 분명히 이득인건 맞는데

 

첫번째 예제를 보면 이게 상당히 어렵다

 

7 2
-37 2 -6 -39 -29 11 -28

 

이걸 정렬하면

 

-39 -37 -29 -28 -6 2 11

 

근데 이제 논리대로라면, -39가 더 머니까 마지막으로 가져가야할거고..

 

그래서 가까운 양수 방향의 11로 먼저 가서 2,11을 가져오면 22를 쓰고

 

다음 음수 방향으로 갈건데, 책을 2권씩 들 수 있으니까

 

-28, -6을 들어서 56

 

-37, -29를 들어서 74

 

다음 -39로 1권 들면... 22+56+74+39 = 191이네

 

근데 정답은 131이란 말이지 그러면 틀렸다는 소리인데

 

-------------------------------------------------------------------------------------------------------------------------------------

 

어쨌든 -39를 마지막에 들어야하는건 무조건 맞을텐데..

 

그래야 -39만큼 돌아가는 거리를 이득보니까

 

그런데 위 결과에서 -37 -29을 들고 -37만큼 다시 돌아가는게 너무 손해같다

 

-39 -37을 들고 안돌아가는게 가장 이득이 아닐까?

 

-29 -28을 들고 29만큼 돌아가고

 

-6을 들고 6만큼 돌아가고

 

그러면 음수 방향을 12 + 58 + 39 = 109만에 해결할 수 있다

 

이전에 56 + 74 + 39 = 169 걸리던 것이 60이나 아낄 수 있다는 소리지

 

---------------------------------------------------------------------------------------------------------------------------------

 

조금 더 생각해서 순방향으로 그리디하게 순회할 생각을 하지 말고

 

한번 더 미래를 생각해서 역방향으로 생각을 해보라는 소리지

 

내림차순으로 정렬시키지 않고 오름차순으로 정렬된 상태에서 정방향으로 순회하면,

 

최대한 이동해서 m개 집고 0으로 돌아오면 최선의 선택같지만, 위처럼 미래를 내다보지 못한 선택이 된다..

 

음수방향, 양수방향의 배열을 내림차순으로 정렬시키고, 정방향으로 순회할때,

 

매번 순회하면서 m개씩 집어가고 0번 원소의 2배를 하면 그것이 놀랍게도 매 순간의 최선의 선택이 된다

 

정리하면

 

1) 음수방향과 양수방향을 따로 모으고

 

-39 -37 -29 -28 -6 

2 11

 

2) 음수 방향의 최댓값과 양수 방향의 최댓값을 비교해서, 더 큰 쪽은 마지막에 움직인다

 

2 11

-39 -37 -29 -28 -6

 

3) 두 배열을 모두 내림차순으로 정렬하고

 

11 2

-39 -37 -29 -28 -6

 

4) 그러면 두 배열을 정방향으로 순회해서 m개씩 집어간다.

 

내림차순으로 정렬된 상태에서 m개씩 무조건 집어가는게 순간에서 최선의 선택(심지어 미래를 생각하면서)이 된다.

 

그럴때 0번 원소의 2배를 더해가면 된다

 

11 2 >> 11*2 = 22

 

-39 -37 >> 39*2 = 78

 

-29 -28 >> 29*2 = 58

 

-6 >> 6*2 = 12

 

22 + 78 + 58 + 12 = 170

 

5) 그런데 마지막에 이동할때는 다시 돌아가지 않아도 된다.

 

최초 양수 방향과 음수 방향으로 이동할때를 결정할때 어디가 최댓값인지를 알 수 있고

 

최댓값인 -39 -37은 2배를 하지 않아도 되므로 더한 값에서 최댓값을 빼준다 170 - 39 = 131

 

from sys import stdin

n,m = map(int,stdin.readline().split())

A = list(map(int,stdin.readline().split()))

#A를 오름차순으로 정렬해놓고
A.sort()

minus = []
plus = []

a = 0
b = 0

#음수와 양수방향을 따로 배열에 모아둔다
for i in range(n):
    
    if A[i] < 0:
        
        minus.append(A[i])
        a += 1
    
    else:
        
        plus.append(A[i])
        b += 1

answer = 0

#A배열을 오름차순 정렬했기때문에
#음수방향은 이미 내림차순 정렬(절댓값 기준으로)되어 있고
#양수방향만 내림차순으로 재정렬하면 된다
plus.sort(reverse=True) 

#각 방향을 정방향으로 순회해서 m개씩 집어가는데
#m개씩 집어가서 0번 원소의 2배를 더해준다는 의미는
#m으로 나눈 나머지가 0인 인덱스의 원소의 2배를 더해준다는 의미다.
for i in range(a):
    
    if i % m == 0:

        answer += -2*minus[i]

for j in range(b):
    
    if j % m == 0:
        
        answer += 2*plus[j]

#a가 0이라는 것은 양수방향만 존재한다는 의미다.
#양수방향에서 최댓값은 0번 원소에
if a == 0:
    
    answer -= plus[0]

#b가 0이라는 것은 음수방향만 존재한다는 의미다.
#음수방향에서 절댓값이 최대인 원소는 0번 원소에
#음수를 빼주는건 더해주는거니까
elif b == 0:
    
    answer += minus[0]

#a,b가 0이 아니면, 음수방향 양수방향 둘다 있다
#각 방향에서 절댓값이 최대인 원소를 찾아
#그 방향은 마지막에 가면 다시 돌아가지 않아도 되니 이득을 본다
#다시 돌아가지 않아도 되니, 그 거리만큼을 이미 더해준 값에 빼준다
else:

    answer -= max(-minus[0],plus[0])

print(answer)