[Python] 백준 2212 - 센서 문제 풀이

Overview

BOJ 2212번 센서 Python 문제 풀이
분류: Greedy (그리디)

---

문제 페이지

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

---

풀이 코드

from sys import stdin


def main():
    def input():
        return stdin.readline().rstrip()

    n, k = (int(input()) for _ in range(2))
    sensors = sorted(list(map(int, input().split())))

    if k >= n:
        print(0)
        return

	dists = sorted(list(sensors[i + 1] - sensors[i] for i in range(n - 1)), reverse=True)
    print(sum(dists[k - 1:]))


if __name__ == "__main__":
    main()

행복 유치원 문제 풀이 에서와 같이 크기가 큰 k-1개의 weight를 제거하여 k개의 그룹을 만들어 푼다.
각 그룹의 수신 가능 영역은 센서들 사이의 거리 합과 같다.

---

참고자료

https://journeytosth.tistory.com/16