[알고리즘/그리디] 1316번 : 행복 유치원 - python

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

13164번: 행복 유치원

 

---

• 문제
• 소요시간: 22분 27초

---

• 설계하기(접근방법) 

1. 입력받기

유치원생 수, 조의 개수와

유치원생 키 리스트를 입력받는다

 

2. 구현하기

 

모든 숫자의 차이를 검사해서

가장 큰 차이부터 (조의 개수 - 1)만큼 제거한다

 

모든 숫자의 차이는

첫번째 인덱스와 마지막 인덱스의 차이이다

 

heapq의 자료구조를 이용해서

모든 리스트를 순회하면서 차이를 max_heap의 형태로 넣어준다

즉 최대값이 맨 앞으로 정렬되게 한다

 

그 후 (조의 개수 -1) 만큼 pop을 시키면서

제외할 항목들의 합을 구한다

 

 

3. 출력하기

총 차이의 합에서

(group - 1)번째 까지의 최대 차이들의 합을 

빼주면 최소 값이 나온다

 

 

 

---

• 코드(출력)

import heapq

n, group = map(int,input().split())
kid_list = list(map(int,input().split()))

total = kid_list[-1] - kid_list[0]

h = []


for i in range(n - 1):
    difference = kid_list[i+1] - kid_list[i]
    heapq.heappush(h, -difference)

except_cnt = 0

for i in range(group - 1):
    except_cnt += heapq.heappop(h) * - 1

print(total - except_cnt)

---

• 얻어갈 부분

1. 이전에 heap과 그리디 문제를 풀어서 쉽게 적용할 수 있었다.

2. 총 차이의 합은 항상 리스트의 처음과 끝의 차이로 같으나,  그 중에서 가장 차이가 많이 나는 경우들을 빼줘야 했다. group - 1개만큼 빼려면 데이터가 30만개여도 금방 갱신할 수 있어야하는데, heap을 통해 구현할 수 있었다.

3. max 힙의 경우 heapq에 음수로 push를 해주면 가장 작은 값이 절대값으로 항상 먼저 나오게 된다.heappop을 할 때 -1을 곱해주어 사용하면 된다.