[Problem Solving] 백준 2212번 센서 문제풀이

백준 2212번 문제풀이에 대해서 알아보겠다. 문제 해설은 다음 링크를 확인하면 된다. 문제 해설

2212번: 센서

2212번 센서는 그리드 유형의 문제이다. 문제를 해결하기 위한 최적의 해를 찾아야 한다. 센서 문제는 주어진 센서들 중에서 집중국을 선정하여 센서들 간의 거리가 가장 작게 만드는 것이다. 문제를 풀기 위해서는 다음의 과정을 거쳐야 한다.

 

1. 센서 위치 정보를 내림차순 정렬한다.
2. 각 센서들 사이의 거리를 계산하여 저장한다.
3. 센서들 사이의 거리 정보를 오름차순 정렬한다.
4. k-1번 가장 큰 거리 정보를 제거해준다.
5. 남아있는 거리 정보를 모두 더해준다.

문제에서 제공하는 예제를 통해서 위의 과정을 알아보겠다. n = 6, k =2 센서 위치 정보는 data = [1, 6, 9, 3, 6 ,7], 각 센서들의 거리 정보는 minus=[]이라고 하겠다.

 

1번 과정의 결과 data = [1, 3, 6, 6, 7 ,9], 2번 과정의 결과 minus = [2, 3, 0, 1, 2], 3번 과정의 결과 minus = [3, 2, 2, 1, 0], 4번 과정의 결과 minus = [2, 2, 1, 0], 5번 과정의 결과 5

 

위의 과정을 코드로 작성하면 아래와 같다.

 

n = int(input())
k = int(input())
data = list(map(int, input().split()))

if k >= n:
    print(0)
else:
    data.sort()
    minus = []
    value = 0
    for i in range(len(data)-1):
        minus.append(data[i+1] - data[i])
    minus.sort(reverse=True)

    for i in range(k-1):
        minus.pop(0)
    print(sum(minus))