(BOJ) 13164. 행복유치원

📗문제 설명

문제 바로가기

❓ 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

• 입력
  • 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109
    를 넘지 않는 자연수이다.
• 출력
  • 티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

# 입력
5 3
1 3 5 6 10
#출력
3

💡문제풀이 IDEA

1. k개의 조를 만든다 → k-1개의 가림막을 사이에 껴넣는다.
2. 그렇다면 k-1개의 가림막이 들어가는 공간은 조를 나누는 줄.

• 예시

  • 5,3

  • 1,3,5,6,10

    → 2,2,1,4가 있다.

    1	가림막	3	가림막	5	가림막	6	가림막	10
    	2		2		1		4
    			조 나누기				조 나누기

    3개의 조로 나누어야 한다는것은 2개의 가림막이 들어가야 한다는것.

    가림막 가능한 곳중 2개가 들어가야 함. 그렇다면 가장 작은 티셔츠값을 만들려면 차이가 가장 큰순서대로 가림막을 넣으면 높은 티셔츠값이 들어가지 않게 된다!

👨🏻‍💻문제 풀이 CODE

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