❓ 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.
이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.
# 입력
5 3
1 3 5 6 10
#출력
3
5,3
1,3,5,6,10
→ 2,2,1,4가 있다.
1 | 가림막 | 3 | 가림막 | 5 | 가림막 | 6 | 가림막 | 10 |
---|---|---|---|---|---|---|---|---|
2 | 2 | 1 | 4 | |||||
조 나누기 | 조 나누기 |
3개의 조로 나누어야 한다는것은 2개의 가림막이 들어가야 한다는것.
가림막 가능한 곳중 2개가 들어가야 함. 그렇다면 가장 작은 티셔츠값을 만들려면 차이가 가장 큰순서대로 가림막을 넣으면 높은 티셔츠값이 들어가지 않게 된다!
import sys
input=sys.stdin.readline
def main():
N,K=map(int,input().split())
kids=list(map(int,input().split()))
answer=kindergarden(N,K,kids)
print(answer)
def kindergarden(N,K,kids):
cost=[] # cost를 기록할 list
for i in range(len(kids)-1): # 아이들 사이 갯수만큼
cost.append(kids[i+1]-kids[i]) # cost를 기록
cost.sort() # 정렬
for _ in range(K-1): #cost 중 k-1개의 가장 높은 cost에 가림막을 넣는다. ( pop )
cost.pop()
return (sum(cost))
if __name__=="__main__":
main()
66736KB 228 ms