[백준] 2212 센서 Python 그리디 풀이

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

2212번: 센서

최근 코테 준비로 문제풀이는 많이 하는데 블로그에도 좀 공부한 기록을 해야할 것 같다 gogo !

첨에 문제 읽고 읭? 했다 수신 가능영역 길이가 의미하는 바가 헷갈렸다 

센서들을 정렬한 상태로 그림을 그리면 다음과 같다 
1 ~ 3센서를 포함하는 수신 가능 영역 2와 6 ~ 9 센서를 포함하는 수신가능 영역 3인 경우 최솟값 5가 도출된다. 

내풀이는 다음과 같다 


if 센서개수 <= 집중국 개수: return 0
else:

예를 들어서 예제 1와 같은 입력이라고 치자 오름차순으로 정렬하면 다음과 같다 

1, 3, 6, 6, 7, 9
그리고 각각 이웃한 센서들과의 거리의 차를 구하면 
1 (2) 3 (3) 6 (0) 6 (1) 7 (2) 9 
근데 우리가 써먹을건 센서들이 아니라 이 거리의 차가 중요하다 

그리디 알고리즘처럼 단순하게 생각해보면, 이 거리의 차들중에서 가장 큰 값들을 제거하면 최소값이 될 것 이다 ! 

거리의 차들은 2, 3, 0, 1, 2 이고 
큰 값들을 제거하기 위해서 내림차순으로 정렬하면 3, 2, 2, 1, 0 이다 

근데 우리는 k=2 이므로 두개의 그룹으로 나눈다고 생각할 수 있다 
즉 여기서 거리 3 을 제거하고 연결을 끊는다고 생각하면, 나머지 거리의 차들을 다 더하면 이것이 최소값이 된다. 
이를 파이썬으로는 슬라이싱이라는 매우 간편한 도구를 이용해서 distance[k-1:] 로 짜르고 sum 을 구했다 


여기서 (집중국 개수 -1)을 해야 k개만큼의 그룹으로 분할 할 수가 있다 

# 2212 센서
n = int(input()) # sensor 개수
k = int(input()) # 집중국 개수
sensor = list(map(int, input().split()))

if n <= k:
    print(0)
else:
    sensor.sort()
    distance = [] # 각 센서끼리의 거리의 차를 저장하는 배열
    for i in range(n-1):
        distance.append(sensor[i+1]-sensor[i])
    distance.sort(reverse=True)
    # 가장 큰 값 k-1 개를 뺀
    print(sum(distance[k-1:]))

우하하 왠일로 1트에 성공~~~~