[BOJ] 2212 센서

문제

me

import sys
input=sys.stdin.readline

N=int(input())
K=int(input())
sensors=list(map(int,input().split()))
if K>=N: # 집중국 개수가 센서 개수보다 많으면 수신가능영역 0, 이걸 안하면 런타임에러 뜬다.
    print(0)
    sys.exit()
    
sensors.sort()
distance=[(i,sensors[i+1]-sensors[i]) for i in range(len(sensors)-1)] # 어느 구간인지 명시하기 위해 i를 저장함
distance.sort(key=lambda x:x[1],reverse=True)

pre_i=0
answer=0
for i in range(K-1):
    answer+= sensors[distance[i][0]] - sensors[pre_i] # 구간 사이 거리 계산
    pre_i=distance[i][0]+1
answer+=sensors[len(sensors)-1] - sensors[pre_i]
print(answer)

집중국 개수-1이 구역 개수라고 보면 된다. 그 구역에 집중국 하나가 있으면 처음부터 끝까지 사이 거리가 수신 가능 영역의 길이라고 볼 수 있다.
나는 index도 저장했는데 생각해보니 어차피 distance에서 각 구간 사이의 거리를 더했으니깐 저걸 이용했어도 됐을 것 같다.

solution

import sys
n=int(input())
m=int(input())

# 집중국의 개수가 n 이상일 때
if k>=n:
	print(0) # 각 센서 위치에 설치하면 되므로 정답은 0
    sys.exit()

# 오름차순 정렬
array=list(map(int,input().split(' ')))
array.sort()

# 각 센서 간의 거리를 계산하여 내림차순 정렬
distances=[]
for i in range(1,n):
	distances.append(array[i]-array[i-1])
distances.sort(reverse=True)

# 가장 긴 거리부터 하나씩 제거
for i in range(k-1):
	distances[i]=0
print(sum(distances))

solution

import sys
input = sys.stdin.readline

# 센서의 개수 N(1 ≤ N ≤ 10,000) 입력
N = int(input())
# 집중국의 개수 K(1 ≤ K ≤ 1000) 입력
K = int(input())

sensor = list(map(int, input().split()))
sensor.sort()

dist = []
for i in range(N-1):
    dist.append(sensor[i+1] - sensor[i])
# 거리 내림차순 정렬    
dist.sort(reverse=True)
    
print(sum(dist[K-1:]))

import sys

n=int(input())
k=int(input())
sensor = list(map(int, sys.stdin.readline().split()))
sensor.sort()
dist = []
for i in range(n-1) : #센서 거리 차
    dist.append(sensor[i+1]-sensor[i])

dist.sort()
if k > n : #집중국 수가 크면 센서 위치에 설치하므로 0
    print(0)
else :
    for i in range(k-1) : #오름차순 정렬 후 집중국 수-1 만큼 제외
        dist.pop()
    min = sum(dist)
    print(min)