도서관 (1461번) - 백준 (BOJ)

https://www.acmicpc.net/problem/1461

1461번: 도서관

 

 

백준 - 도서관 (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

이 된다.