[TIL] 99클럽 코테 스터디 18일차 TIL - 그리디: <백준 2212 센서> 문제 풀이 with python

Today's keyword : 

 

 

📌 문제설명

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

센서 문제는 입력으로 센서의 개수와 집중국의 개수, 센서의 위치가 주어지면 모든 센서가 통신 가능하도록 하는 집중국의 수신 가능 영역 거리의 합 중 최소값을 찾는 문제입니다. 

📌 문제풀이

집중국의 수신 가능 영역의 거리의 합을 계산하는 과정을 첫 번째 예시로 그림으로 그려보면 다음과 같습니다. 
센서는 총 6개가 주어지며, 각 센서의 위치는 다음과 같이 주어졌을 때, 센서가 모두 통신할 수 있는 집중국의 위치를 생각해보면 1번처럼 첫번째 센서만 커버하는 집중국 하나와 나머지 센서를 커버하는 집중국으로 분리할 수도 있고, 2번처럼 앞에 있는 4개 센서와 뒤에 있는 2개 있는 센서를 묶을 수도 있습니다. 하지만 두 센서가 커버하는 거리의 합을 최소화해야 하므로, 3번처럼 센서들을 구분할 때 멀리 떨어져 있는 센서들을 다른 그룹으로 묶이도록 해야 합니다. 

 

이를 코드로 구현하면, 센서 간 거리를 계산하고 집중국의 개수-1만큼 반복문을 돌면서 거리가 떨어져 있는 거리들을 순차적으로 제거하면 됩니다. 

n = int(input())  # 센서 개수
k = int(input())  # 집중국 개수
sensor = list(map(int, input().split()))  # 센서 위치 입력

# 예외 처리: 센서 수가 집중국 수보다 적거나 같은 경우
if k >= n:
    print(0)  # 각 센서에 집중국을 설치하면 수신 범위가 0
else:
    sensor.sort()  # 센서 위치 정렬
    # 인접 센서 간의 거리 계산
    distance = [sensor[i+1] - sensor[i] for i in range(n - 1)]
    
    # 내림차순으로 정렬 후, 가장 큰 거리 k-1개를 제거
    distance.sort(reverse=True)
    for i in range(k - 1):
        distance.pop(0)
    
    # 남은 거리의 합이 최소 수신 범위
    print(sum(distance))

 

1. 센서 위치 정렬: 센서 좌표를 오름차순으로 정렬합니다. 정렬된 상태에서 센서 간 거리를 계산하면 쉽게 각 센서 간의 간격을 구할 수 있습니다.
2. 센서 간 거리 계산: 정렬된 센서 간의 거리를 계산하여 distance 리스트에 저장합니다. 이 리스트는 센서가 인접한 거리 간격을 나타냅니다.
3. 가장 긴 k-1개의 거리 제거: 집중국이 k개라면 센서를 k개의 구간으로 분리할 수 있습니다. 따라서, 센서 간 거리 중 가장 긴 k-1개의 구간을 제거하면 집중국 간의 수신 거리를 최소화할 수 있습니다.
4. 남은 거리의 합계 계산: 가장 긴 k-1개의 거리를 제거한 후 남은 거리의 합을 구하면 최소 수신 거리가 됩니다.
5. 예외 처리: k >= n인 경우에는 센서가 각 집중국에 하나씩 분리되므로 수신 범위가 0이 됩니다.

 

 

📌 오늘의 회고 

문제 이해가 어려웠다..

 

 

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL