[백준] 13164번 파이썬 - 그리디, 정렬

문제요약 (13164번. 행복 유치원)

 

13164번: 행복 유치원

 

 

풀이를 위한 부연 설명

• 아이디어를 떠올리는 것이 중요한 문제이다.
• 먼저 유치원생들 간의 키 차이를 diff에 저장한다.
  • 인덱스 에러에 주의한다.
• n-k개의 diff 값을 더하면 구하려는 값이 나온다.

 

• 그리디와 정렬에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다.

 

[코테 알고리즘] 그리디 / 관련 문제

[코테 알고리즘] 정렬 / 관련 문제

 

코드 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
kids = list(map(int, input().split()))

kids.sort()

diff = [0] * (n-1)

for i in range(n-1):
    diff[i] = kids[i+1] - kids[i]

diff.sort(reverse=True)

print(sum(diff[k-1:]))

 

 

 

기억할 점

• 정렬의 기준에 대해 생각해보고
• 문제를 푸는 아이디어를 떠올려야한다.