[BOJ] 13164 - 행복 유치원 (Python)

 

 

아이디어

 

원생들의 키 차이를 정렬하여 차이가 큰 값들을 제외하고 나머지 합을 구한다.

차이가 큰 값들은 어디에 포함되더라도 비용에 포함되므로 경계를 나눠 분리해야 비용을 줄일 수 있다.

 

 

풀이

 

원생들의 키 차이를 리스트 D에 추가하여 정렬한 후, K-1개의 큰 값들을 제외한 나머지 값들의 합을 구해 출력한다.

리스트 D의 길이는 N-1이므로 뒤에서부터 K-1개의 값을 제외하려면 D[:N-K]를 사용하면 된다.

 

N, K = map(int, input().split())
H = list(map(int, input().split()))
D = []
for i in range(N-1):
    D.append(H[i+1]-H[i])
D.sort()
print(sum(D[:N-K]))

 

 

리스트 컴프리헨션보다 for문에서 append하는 코드가 1.7배 정도 더 빨랐다.

# 1.
D = sorted([H[i+1]-H[i] for i in range(N-1)])

# 2. 더 빠른 코드
D = []
for i in range(N-1):
    D.append(H[i+1]-H[i])
D.sort()