[Python] 백준 13164 - 행복 유치원 문제 풀이

Overview

BOJ 13164번 행복 유치원 Python 문제 풀이
분류: Greedy (그리디)

---

문제 페이지

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

---

풀이 코드

from sys import stdin
from heapq import heappop, heappush


def main():
    n, k = map(int, stdin.readline().split())
    heights = list(map(int, stdin.readline().split()))

    if k == n:
        print(0)
        return

    hq = []
    for i in range(1, n):
        heappush(hq, -(heights[i] - heights[i - 1]))

    res = heights[-1] - heights[0]
    for i in range(k - 1):
        res -= -heappop(hq)

    print(res)


if __name__ == "__main__":
    main()
    

유치원생들을 k개의 그룹으로 나누어 저장하려 하지 말고 반대로 생각해야 한다.
유치원생들이 모두 같은 조 일때의 총 비용을 구하고, 여기서 k - 1개의 비용을 뺀다. 티셔츠 비용이 큰 순서대로 빼면 답을 구할 수 있다.