* 백준 2212번 - 센서

Gyuhan Park·2021년 12월 8일
0

코딩테스트 정복

목록 보기
36/47

고속도로 위에 N개의 센서, K개의 집중국을 세울 수 있다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능하며, 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오.

# 틀린 코드

아이디어를 생각해내지 못해서 틀린 코드가 없다. 일단 출력값을 이해못했다. 예시대로면 센서를 정렬했을 때 [1, 3, 6, 6, 7, 9] 니까 2에 1개, 7에 1개 두면 각각 수신 가능영역이 1, 2로 최솟값이 3 아닌가? 어떻게 5지?
이걸 해결못하니 코드를 짤 수 조차 없었다. 집중국이 여러개니까 통신할 그룹을 나눠야겠다라는 생각정도?

문제설명이 모호하다는 것을 나만 느낀 것이 아니였다.(;;)
집중국을 좌표에 설치한다는 개념이 아니였다. 수신가능영역의 거리는 수신이 가능한 전체 영역의 길이다.

그래서 예제1에서는 [1, 3], [6, 6, 7, 9] 로 그룹을 나눌 수 있는데,
한 집중국이 1부터 3까지의 구간을 수신하여 2만큼이 수신가능한 영역의 길이고,
또다른 집중국이 6부터 9까지의 구간을 수신하여 3만큼 수신가능한 영역의 길이로 합값은 5다.

# 정답 코드

아이디어 문제도 있지만 문제설명을 명확히 써주었다면 충분히 생각해낼 수 있었던 문제라고 생각한다. 문제를 이해하고 코드로 옮기는 건 어렵지 않았다.

import sys
input = sys.stdin.readline
N = int(input())
K = int(input())
sensors = list(map(int, input().split()))
gap = []

sensors.sort()

if N < K:
  print(0)
else:
  for i in range(1, N):
    gap.append(sensors[i] - sensors[i-1])
  gap.sort()

  for _ in range(K-1):
    gap.pop()

  print(sum(gap))
profile
단단한 프론트엔드 개발자가 되고 싶은

0개의 댓글