[solved.ac 골드5] 2212_센서 (파이썬, 정렬, 그리디)

https://github.com/mangbaam/CodingTest

GitHub - mangbaam/CodingTest: 프로그래머스, 백준 등 코딩테스트 풀이를 기록하는 저장소입니다.

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한 사항

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

예제

---

나의 풀이

문제를 이해하는데 너무 오래 걸렸다. 문제 설명이 부실한건지 내 독해력이 부실한 건지는 모르겠다...

헷갈릴만한 부분은 집중국도 정수 위치에 놓여야 한다는 말은 없었다는 것이다. 처음에 집중국도 정수 위치에 존재해서 양쪽으로 같은 범위만큼 수신할 수 있도록 해야하는 줄 알았다.

그저 최대 k개의 집중국으로 n개의 센서를 빠짐 없이 포함하도록 하면 된다.

2번째 예제를 예시로 들겠다

1.

초기 상태이고, 위의 주황색 숫자는 센서 간의 간격을 의미한다.

코드 상에서 위와 같이 나타내려면 센서의 위치를 오름차순으로 정렬하는 과정이 필요하다.

2.

최대 5개의 집중국을 설치할 수 있고, 모든 센서를 커버할 수 있어야 한다는 것은 센서들을 최대 5개의 그룹으로 나누어야 한다는 것이다.

현재 상태는 1개의 집중국이 설치된 상태라고 볼 수 있다. 이 1개의 집중국은 [3, 20] 의 센서를 커버한다.

3.

간격 중 가장 큰 값인 3을 지우면 위와 같이 0, 14로 나뉜다. 현재 상태는 2개의 집중국이 설치된 것이고, [3, 3]을 커버하는 집중국과 [6, 20]을 커버하는 집중국이 있는 상태이다.

가장 큰 간격을 끊어내야 최소 수신 거리의 합을 구할 수 있다.

4.

다음으로 현재 가장 큰 간격인 3을 제거하면서 연결을 끊었다. 이렇게 하면 현재 3개의 집중국이 설치된 것이고, [3, 3]을 커버하는 집중국과 [6, 15]을 커버하는 집중국과 [18, 20]을 커버하는 집중국이 있는 상태이다.

5.

다음으로 현재 가장 큰 간격인 2를 제거하면서 연결을 끊었다. 이렇게 하면 현재 4개의 집중국이 설치된 것이고, [3, 3]을 커버하는 집중국과 [6, 8]을 커버하는 집중국과 [10, 15]을 커버하는 집중국과 [18, 20]을 커버하는 집중국이 있는 상태이다.

6.

다음으로 현재 가장 큰 간격인 2를 제거하면서 연결을 끊었다. 이렇게 하면 현재 5개의 집중국이 설치된 것이고, [3, 3]을 커버하는 집중국과 [6, 8]을 커버하는 집중국과 [10, 10]을 커버하는 집중국과 [12, 15]을 커버하는 집중국과 [18, 20]을 커버하는 집중국이 있는 상태이다.

 

총 4번의 연결을 끊어내면서 5개의 영역으로 나눌 수 있었다. 최종적으로 각 집중국이 커버하는 영역은 0, 2, 0, 3, 2 만큼이고, 이 영역의 합인 7이 답이 된다.

코드

n, k = int(input()), int(input())
sensors = sorted(map(int, input().split()))
print(sum(sorted([sensors[i + 1] - sensors[i] for i in range(n - 1)], reverse=True)[k - 1:]))

• n, k를 입력 받는다
• 센서의 위치를 받아 정렬해서 sensors에 담는다
• 간격을 내림차순 정렬한 후 상위 (k - 1)개를 제외한 것의 합을 출력한다

 

채점 결과