백준 1092 : 문제링크

  • 문제유형 :

    • 탐욕 알고리즘

  • 설명

    • 정렬만 수행하면 되므로 시간복잡도는 O(NlogN)
    • 각 센서를 오름차순으로 정렬한다
    • 각 센서 사이의 거리를 계산한다
    • 가장 거리가 먼 순서대로 k - 1개의 연결 고리르 제거한다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    import sys

    n = int(input())
    k = int(input())

    if k >= n:
        print(0)
        sys.exit()

    array = list(map(int, input().split(' ')))
    array.sort()

    distance = []
    for i in range(1, n):
        distances.append(array[i] - array[i - 1])
    distance.sort(reverse=True)

    for i in range(k - 1):
        distances[i] = 0
    print(sum(distances))