[백준] 2212 센서 Python 그리디 풀이
https://www.acmicpc.net/problem/2212
2212번: 센서
첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있
www.acmicpc.net
최근 코테 준비로 문제풀이는 많이 하는데 블로그에도 좀 공부한 기록을 해야할 것 같다 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:]))
