백준 - 센서 2212번
👏 key point
사실 문제를 이해하는 데 있어서 상당히 오랜 시간이 걸린 문제이다.
예를 들어 입력받은 리스트가 1 6 9 3 6 7이고
좌표상으로 표현하면 다음과 같다.
Q. 만약 집중국이 하나라면 어떨까??
A. 1~9까지의 모든 센서들을 감지해야 하므로 수신 가능 영역의 길이는 8이다.
Q. 그렇다면 집중국의 개수가 2개라면 어떨까?
A. 이렇게 구간이 제일 긴 구간을 제외하고 나누게 되면 수신가능 영역의 길이는 5로 가장 짧게 집중국을 설치할 수 있을 것이다.
따라서 필자는 좌표상 평면을 구현하기 위해 센서들을 오름차순으로 정렬하고
바로 옆에 있는 센서들끼리의 거리들을 구하여 배열로 나타낸 distance를 생성하였다. 그리고 그 배열을 다시 정렬하여 가장 큰 값을 빼는 과정을 반복하였다.(k-1번)
그렇게 하여 남은 구간들의 합이 바로 수신 가능한 영역의 최솟값이 된다. 자세한 내용은 코드를 보면 알 수 있다.
🎂 코드
n = int(input())
k = int(input())
sens = list(map(int, input().split()))
if n <= k:
print(0)
else:
#센서들을 오름차순으로 정렬
sens.sort()
distance = []
#distance = 옆에 있는 센서들끼리의 거리들을 구한 배열
for i in range(1,n):
distance.append(sens[i] - sens[i-1])
distance.sort()
#distance를 정렬하여 k-1만큼 pop
for _ in range(1,k):
distance.pop()
#남은 구간들의 합 = 수신 가능영역의 최솟값
print(sum(distance))
Author And Source
이 문제에 관하여(백준 - 센서 2212번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@turtle601/백준-센서-2212번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)