[백준] 11000 강의실 배정

✔️ 문제 링크

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

💡 핵심 아이디어

1️⃣ 기지국을 어디든 놓게 되어도 수신 가능 영역은 센서간의 가장 가까운 거리들의 합으로 구해지게 된다.

2️⃣ K개의 구역으로 나눠 기지국을 설치하는데 이때, 그룹간 거리는 고려하지 않는 점을 이용하여 센서간 거리가 긴 순서대로 잘라 그룹을 지어 수신 가능 길이를 최소로 하게 해 준다.

⭐️ 소스 코드

if __name__ == '__main__':
    N = int(input())
    K = int(input())
    sensor_loc = list(map(int, input().split()))

    sensor_loc.sort()

    sensor_loc_dist = []

    for i, sensor in enumerate(sensor_loc):
        if i == 0:
            temp = sensor
            continue

        sensor_loc_dist.append(sensor - temp)
        temp = sensor

    cnt = 1
    while cnt <= K-1:
        if len(sensor_loc_dist) == 0:
            break
        m = max(sensor_loc_dist)
        sensor_loc_dist.remove(m)
        cnt += 1

    print(sum(sensor_loc_dist))