[Python/백준] 13164 행복 유치원

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

13164번: 행복 유치원

<문제 해설>

그리디 문제이다.

주어진 값 들의 사이 값들을 전부 분석해 저장한뒤 N-K만큼 빼내면 조를 K개 정했을때 필요한 금액이 된다.

이유는

1 | 3 | 5 | 6 | 10

이렇게 있다고 했을 때 3개 조를 만들라면 2 : 2 : 1 로 조를 나눠야하고 2명씩 묵는 조가 2개가 나와야한다.

그리고 이 2개의 조안에서 차이를 보면 되기 때문이다.

또한 2개의 조를 만들라고 했을 땐  3 : 2 로 가는 것보다 4 : 1 로 가는 것이 더 작다.

3 : 2는

(2 + 2) + (1 + 4) = 9

4 : 1 은

(2 + 2 + 1) = 5

여기서 느낀 것이 있는가?

가장 작은 값을 구하려면 N - K만큼인 3개의 수만 더해줘야 한다는 것이다.  그래서 N - K 만큼 빼서 더한 것이 필요한 금액이 되는 것이다.

차이값들을 저장할때 heap최소 힙으로 저장하고 N-K만큼 pop시켜 output에 저장하면 된다.

자세한건 아래 예시를 보자.

<예시>

예시 1을 보여주겠다.

빨간색 줄은 N개값 사이의 차이값들이다. 이중 가장 작은 값 1,2를빼서 더해주면 된다.

그렇다면 K = 2일땐 어떻게 될까?

1~6 이 한그룹 10이 한그룹이 되는 5가 답인데 N-K = 3 작은값 3개를 빼서 더해주니 5가 되는 것을 볼 수 있다.

<코드>

import sys
import heapq

N, K = list(map(int,sys.stdin.readline().split()))
tail = list(map(int,sys.stdin.readline().split()))
heap = []
for i in range(1,N):
    diff = tail[i] - tail[i-1]
    heapq.heappush(heap,diff)

output = 0
for j in range(N-K):
    output += heapq.heappop(heap)

print(output)00