[백준] 13164번 : 행복 유치원

13164번: 행복 유치원

13164번: 행복 유치원

🤔 문제분석

이전에 비슷한 문제의 유형을 풀어보아서 문제를 쉽게 해결 할 수 있었습니다. 정렬을 한뒤에 각 이웃하는 원소끼리 diff를 구한뒤 가장 큰 diff를 k-1개를 pop 시킨다면 k개의 그룹이 생깁니다. k-1개의 뺀 나머지 diff를 모두 합치게된다면 원하는 값이 나옵니다.

잘 생각해보면 diff를 모두 더한값이 정답이 되는 과정을 예를 들어본다면 1,3,5 가 있다고 한다면 diff 값은 2, 2가 되는데 여기서 가장 큰 원소와 작은원소는 1과 5이고 2+2 를 더한값이 나오게 됩니다.

💻 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

arr = list(map(int, input().split()))

temp = []
for i in range(N):
    temp.append((arr[i], i))
    
temp.sort()

diff = []
for i in range(1, N):
    diff.append(temp[i][0] - temp[i-1][0])
    
diff.sort()

for _ in range(K-1):
    diff.pop()

print(sum(diff))

🎯 피드백 및 개선사항

직전에 비슷한 유형을 풀어보아서 문제를 어떻게 접근해야할지 빠르게 파악하였습니다.