[Boj/백준] 13164 Python

문제출처: https://www.acmicpc.net/problem/13164

13164번: 행복 유치원

 

 

1. 문제 접근 방식

고민을 길게 했다,,,

그러다가

각 인접하는 원소의 크기차이를 배열로 만들고

ex) 1 3 5 6 10이면 ( 2 2 1 4 )

k가 1이면 2+2+1+4

2이면 2+2+1

3이면 2+1 ...

처럼 k값이 한 개 오를때마다 가장 큰 원소를 힙을 이용해서 heappop했다.

 

 

2. 내가 푼 코드

import sys
import heapq

n,k = map(int,sys.stdin.readline().split())

arr = list(map(int,sys.stdin.readline().split()))
heap = []
heapq.heapify(heap)
for i in range(len(arr)-1): # 0 1 2 3 4
    heapq.heappush(heap,(-arr[i+1]+arr[i]))

for i in range(k-1):
    heapq.heappop(heap)

print(abs(sum(heap)))

 

 

3. 결과 및 느낀점

브루트포스가 아니면 그리디라고 생각한다.

항상 최선의 선택이 존재한다는 말이 와닿았다.