[BOJ] Python 백준 센서(2212)

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

 

 

그리디 + 정렬 문제이다.

주어진 직선상의 좌표에서 정렬을 진행한 후, 그 사이에 값의 차이 중 가장 큰 부분들을 배열에 저장하여, K개의 영역만 남도록

K-1개 만큼 사이의 거리를 없애줌으로써 영역을 분리해준다. 

그 후, 다 더하면 영역사이의 거리 최솟값을 구할 수 있다.

# https://www.acmicpc.net/problem/2212
# 다시 풀어볼 문제
import sys
input = sys.stdin.readline

N = int(input())
K = int(input())
s = list(map(int,input().split()))
s.sort()

if K >= N:
    print(0)
    exit()

dist = []
for i in range(1,N):
    dist.append(s[i]-s[i-1])

dist.sort(reverse=True)

for i in range(K-1):
    dist.pop(0)

print(sum(dist))

 

회고.

그리디 문제는 문제 이해나 문제 접근자체에 어려움을 느끼는거 같다... 이번에도 문제를 어떻게 해석하고 접근할지를 고민하다가 못풀었다... 더 열심히 그리디 문제를 접해봐야할거 같다.