[백준] 2212 : 센서 (파이썬)

그리디 문제

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

---

문제 설명

고속도로 위에 최대 K개의 집중국을 세워 N개의 센서에 도달해야 한다.

• 이때, N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 한다.
• 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

접근 방식

그리디

우리는 최대 K개의 집중국을 세워 모든 N개의 센서에 도달하는 것이 목표이다.

즉, 최대 K개의 집중국을 세워 n(n1,n1,..)-k(k1,k2,..)의 최솟값의 합을 구하는 것이 목표이다.

여기서 N개의 센서와 K개의 집중국이 의미하는 바가 무엇인지 알아보자.

• N개의 센서 : 우리가 도달해야 하는 센서의 개수로, 각 센서는 원점으로부터의 정수 거리의 위치에 놓여 있다.
• K개의 집중국 : 세울 수 있는 집중국의 개수로, 센서-센서 간의 거리를 하나 뛰어넘게 해주는 역할을 한다.
  • 만약, 집중국이 2개라면 센서-센서 간의 거리를 하나 뛰어넘을 수 있다.
  • 만약, 집중국이 3개라면 센서-센서 간의 거리를 2개 뛰어넘을 수 있다.

예시 
1 3 6 6 7 9 35
0 2 3 0 1 2 26

1) K = 1일 때
센서-센서 간의 간격이 가장 큰 곳에 집중국을 두어 해당 센서로부터 수신할 영역의 길이를 0개 제외시킨다.
            🗼
1 3 6 6 7 9 35
  2 3 0 1 2 26
정답 : 2 + 3 + 0 + 1 + 2 + 26 = 8


2) K = 2일 때
센서-센서 간의 간격이 가장 큰 곳에 집중국을 두어 해당 센서로부터 수신할 영역의 길이를 1개 제외시킨다.
    🗼      🗼
1 3 6 6 7 9 35
  2 3 0 1 2 26
정답 : 2 + 3 + 0 + 1 + 2 = 8


3) K = 3일 때
센서-센서 간의 간격이 가장 큰 곳에 집중국을 두어 해당 센서로부터 수신할 영역의 길이를 2개 제외시킨다.
  🗼🗼      🗼
1 3 6 6 7 9 35
  2 3 0 1 2 26
정답 : 2 + 0 + 1 + 2 = 5

1. 인접한 센서들 사이의 거리 차이를 계산하여 차이 배열을 만든다.
2. 차이 배열을 정렬하여 가장 큰 차이들을 선택한다.
3. 가장 큰 K-1개의 차이를 잘라내고, 나머지 차이들의 합을 최소 비용으로 반환한다.

---

💡 풀이 코드 (성공)

import sys 
sensor = int(sys.stdin.readline())
home = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()

def sol(sensor, home, arr):
    diff = []
    for i in range(1, sensor):
        diff.append(arr[i] - arr[i - 1])
    diff.sort()
    select = max(sensor - home, 0)
    print(sum(diff[:select]))

if sensor <= 1:
    print(0)
else:
    sol(sensor, home, arr)

주요 로직

센서의 개수 N(1 ≤ N ≤ 10,000)이므로 N이 2 이상일 때만 sol 함수를 호출하여 차이(diff) 배열을 구한 후 결과값을 출력하도록 해주었다.

if sensor <= 1:
    print(0)
else:
    sol(sensor, home, arr)

 

또, 기지국의 갯수가 센서의 갯수보다 큰 경우도 있을 수 있으므로 다음과 같은 예외 처리를 해주었다.

• 기지국의 갯수가 센서의 갯수보다 큰 경우가 의미하는 바는 기지국을 센서의 모든 위치에 세우고도 기지국이 남는다는 뜻이다.
• 이러한 경우에는 센서로부터 수신해야 하는 영역의 길이의 합이 0이므로 select를 0을 만들어 아무것도 합산하지 않게 하면 된다.

select = max(sensor - home, 0)
print(sum(diff[:select]))

---

참고문헌

https://velog.io/@jkh9615/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-11000-%EA%B0%95%EC%9D%98%EC%8B%A4-%EB%B0%B0%EC%A0%95-Java-wskzqzk6

[알고리즘] 백준 2212 센서 Java

https://journeytosth.tistory.com/16

[알고리즘] 백준 2212번 : 센서