백준 1461 : 문제링크

  • 문제유형 :

    • 탐욕 알고리즘

  • 설명

    • 일직선상에 책들을 순서대로 위치시킨다
    • 0보다 큰 책들과 0보다 작은 책들을 나누어서 처리한다
    • 음수와 양수 좌표를 위해 두 개의 우선순위 큐를 이용한다
    • 마지막 책을 놓을 때는 다시 0으로 돌아올 필요가 없기 때문에, 가장 먼 책을 마지막으로 놓는다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    import heapq

    n, m = map(int, input().split(' '))
    array = list(map(int, input().split(' ')))
    positive = []
    negative = []

    largest = max(max(array), - min(array))

    for i in array:
        if i > 0:
            heapq.heappush(positive, -i)
        else:
            heapq.heappush(negative, i)

    result = 0

    while positive:
        result += heapq.heappop(positive)
        for _ in range(m - 1):
            if positive:
                heapq.heappop(positive)

    while negative:
        result += heapq.heappop(negative)
        for _ in range(m - 1):
            if negative:
                heapq.heappop(negative)

    print(-result * 2 - largest)