Skip to main content

13164 - 행복 유치원

info

문제 보기: 13164 - 행복 유치원
소요 시간: null (25분정도 고민하다 발상 안될 것 같아서 포기)
풀이 언어: python
체감 난이도: 3️⃣~4️⃣
리뷰 횟수: ✅

풀이 키워드

스포주의

그리디

I HATE GREEDY

풀이 코드

info

메모리: 66600 KB
시간: 212 ms

import sys
input = sys.stdin.readline

def solution():
    n, k = map(int, input().split())
    data = list(map(int, input().split()))
    
    # 인접 값끼리의 차를 구하고
    # 가장 큰 k-1개의 차를 제외하고 다 더하면 답이 됨
    
    subs = [0] * (n-1)
    for i in range(n-1):
        subs[i] = data[i+1] - data[i]
        
    subs.sort()
    print(sum(subs[:n-k]))


if __name__ == '__main__':
    solution()

풀이 해설

입력이 이미 오름차순 정렬되어 있으므로, 인접 값끼리의 차를 따로 저장한다.
1에서 구한 값을 오름차순 정리한다.
1의 결과에서 값이 큰 순서대로 k-1개 값을 제외한 모든 원소들을 더한다.

무슨 원리임?

예를 들어 data[0] ~ data[2] 까지를 한 팀으로 나누었다고 가정하자.
그렇다면 data[2] - data[0] 값을 구해야 하는데, 이는 (data[1]-data[0]) + (data[2]-data[1])과 같다.

이 값을 최소로 하고 싶다면, 팀 사이의 경계에 가장 높은 차를 두면 된다.
경계에 위치한 값은 결과값 계산에서 제외되기 때문이다.

풀이 키워드
풀이 코드
풀이 해설