[Python] 백준 : 13164 행복 유치원

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

13164번: 행복 유치원

ANS

N,K = map(int, input().split())
childlist = list(map(int, input().split()))
priceList = [0] * (N-1) #이웃한 값과의 차이를 나타낼 리스트
for idx in range(N-1): #이웃 값과의 차이 구하기
    priceList[idx] = childlist[idx+1] -childlist[idx]
priceList.sort()
ans = sum(priceList[:N-K])
print(ans)

N이 아주 클 수 있기 때문에 brute-force로 풀면 안 될것이라는 생각을 하고 문제 풀이를 시작했다. 학생들을 리스트로 받을 때 순서대로(정렬이 된 상태로) 들어온다는 것을 기초로 해 따로 sort를 하지 않았고, 인접한 학생들의 gap을 구하기 위해서 priceList에 for문을 돌며 저장해주었다.

 

만일 문제에서 주어진 TC와 같이 5명의 학생을 3개의 조로 나눠야 한다면

A | B | C | D | E에서 막대기 두 개를 제거해야 한다.(순서 관련 없이 2개의 |를 제거하면 3개의 구역으로 묶을 수 있다. 이것을 고려해서 sum(priceList[:N-K])를 해주면 된다!