BOJ 13164 - 행복 유치원

문제

백준 온라인 저지 - 13164번

풀이 과정

그리디 문제가 항상 그렇듯 풀이는 정말 간단한데 아이디어를 생각하는게 어려운 문제였습니다.

K 개의 그룹을 만들어야하고 모든 키 정보는 양수라는 점을 이용해서
처음에는 2명 이상의 그룹의 수를 최소화 하는 방향으로 접근했습니다.
여기서 그룹의 인원수는 무조건 적은게 좋다고 생각해서 2인 그룹 의 수를 최소화 할 수 있는 방향으로 고민했었습니다.
그런데 이렇게 접근하니까 최적해를 고르는 명확한 기준을 잡기가 어려웠고 상황에 따라서는 모순이 생기는 경우도 있었습니다.

결국 다른 방법이 필요했는데 타 블로그의 풀이를 참고해서 문제를 해결할 수 있었습니다.
그룹의 수가 K 일 때 그룹의 경계는 K - 1 개 만큼 존재합니다.
여기서 이 경계 값들을 최대화해서 그룹을 만들면 그룹 내부의 최소 및 최대의 차이 값은 최적해가 됩니다.

따라서 내림차순으로 정렬을 수행한 다음 상위 K - 1 개의 인접 차이 값을 제외한 나머지의 합이 우리가 찾는 답이 됩니다.

코드

import sys


N, K = list(map(int, sys.stdin.readline().split()))
children = list(map(int, sys.stdin.readline().split()))


def solution():
    diff = []
    for i in range(len(children) - 1):
        diff.append(children[i + 1] - children[i])

    diff.sort(reverse=True)
    answer = sum(diff[K - 1:])

    return answer


print(solution())