[Python] 백준 풀기 2212 - 센서

파이썬 백준 2212번

골드 5

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

2212번: 센서

 

 

 

 

 

문제 보기

분류: 그리디 알고리즘, 정렬

 

 

 

 

 

문제 풀기

예제 입력 1 번에 대한 경우를 그림으로 나타내면 위와 같다.

집중국이 커버칠 수 있는 최소한의 거리를 찾으면 가장 넓은 구간 3 을 제외하고 2, 1+2 를 선택하여 최솟값을 이루는 집중국을 위치시킬 수 있다.

 

 

임의로 주어진 센서의 순서를 오름차순으로 정렬을 하고, 그 숫자(센서) 간의 간격을 모두 정리를 한다.

제일 거리의 차가 큰 값은 집중국에서 커버치지 않도록 하여 최솟값을 정하는 데 있어 빠지게 한다. 이는 정렬 저장된 거리 값 리스트 dist_ls 에서 뒤부터 K-1 개를 제거한다고 보면 된다.

따라서, dist_ls[:N-K] 구간의 합을 통해 최솟값을 구할 수 있다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline


def fnMinimumDistance(N, K):
    dist_ls = []
    
    sensor_ls.sort()
    # print(sensor_ls)            # test print
    
    for i in range(0, N - 1):
        dist_ls.append(sensor_ls[i+1] - sensor_ls[i])
    
    # print(dist_ls)          # test print
    dist_ls.sort()
    # print(dist_ls)          # test print
    
    # print(dist_ls[:N-K])            # test print
    
    print(sum(dist_ls[:N-K]))


if __name__ == "__main__":
    N = int(inputdata().strip())
    K = int(inputdata().strip())
    sensor_ls = list(map(int, inputdata().split()))
    
    fnMinimumDistance(N, K)

 

 

 

 

 

추가 하기

import sys
inputdata = sys.stdin.readline


def fnMinimumDistance(N, K):
    dist_ls = []
    
    sensor_ls.sort()
    print(sensor_ls)            # test print
    
    for i in range(0, N - 1):
        dist_ls.append(sensor_ls[i+1] - sensor_ls[i])
    
    print(dist_ls)          # test print
    dist_ls.sort()
    print(dist_ls)          # test print
    
    print(dist_ls[:N-K])            # test print
    
    print(sum(dist_ls[:N-K]))


if __name__ == "__main__":
    N = int(inputdata().strip())
    K = int(inputdata().strip())
    sensor_ls = list(map(int, inputdata().split()))
    
    fnMinimumDistance(N, K)



# 6
# 2
# 1 6 9 3 6 7

# [1, 3, 6, 6, 7, 9]
# [2, 3, 0, 1, 2]
# [0, 1, 2, 2, 3]
# [0, 1, 2, 2]

# 5


# 10
# 5
# 20 3 14 6 7 8 18 10 12 15

# [3, 6, 7, 8, 10, 12, 14, 15, 18, 20]
# [3, 1, 1, 2, 2, 2, 1, 3, 2]
# [1, 1, 1, 2, 2, 2, 2, 3, 3]
# [1, 1, 1, 2, 2]

# 7