[백준] 2212 센서 (Python/파이썬)

<문제 링크>

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

2212번: 센서

<풀이 전략>

1. 그리디 알고리즘으로 분류되는 문제인데 대부분의 그리디 문제가 그렇듯이 그리디인 걸 알고 나면 쉽다. 그리디인 걸 알고 확신하기까지가 어려워서 그렇지...
2. 센서와 집중국 간의 거리를 최소화 해야되기 때문에 센서 간 거리가 가장 큰 지역이 집중국 수신 영역 내에 포함되지 않도록 해야된다.
3. 따라서 센서 간 거리를 구해서 가장 거리가 큰 지역 K - 1개를 총 지역에서 빼주면 된다.
   • 텍스트로 써서 좀 헷갈리는데 그림으로 그려보면 더 쉽게 이해할 수 있다.
4. 어차피 거리를 구하는 거기 때문에 집중국을 설치하는 정확한 위치는 필요 없다.
5. 그 외에 센서 좌표 중복 제거하는 거랑 집중국 개수가 더 많을 때 예외처리만 신경 써주면 된다.

6. 추가로 15553 난로(https://www.acmicpc.net/problem/15553) 문제도 매우 유사하니까 한번 풀어보면 좋을 것 같다.

 

<정답 코드>

# 220903 2212 센서

# 정답코드

import sys
input = sys.stdin.readline

# N: 센서의 개수, K: 집중국의 개수 sensor: 센서의 좌표
N = int(input())
K = int(input())
sensor = list(map(int, input().split()))

# 센서 좌표 중복 제거 후 정렬
sensor = list(set(sensor))
sensor.sort()

# 집중국 개수가 정렬된 센서 개수보다 많거나 같으면 수신 가능 영역은 0이다.(각 센서마다 설치)
if K >= len(sensor):
    print(0)
# 센서 개수가 더 많을 때
else:        
    # 각 센서 간의 거리를 구한다.
    distance = [0]
    for i in range(1, len(sensor)):
        distance.append(sensor[i] - sensor[i-1])

    # 센서 거리 내림차순으로 정렬
    distance.sort(reverse=True)

    # total_distance: 센서 간 거리의 합
    total_distance = sum(distance)

    # 센서 간 거리가 가장 큰 영역 K-1개를 거리 총합에서 빼준다.
    for i in range(K - 1):
        total_distance -= distance[i]

    print(total_distance)