문제 바로가기
문제:
행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다. 이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.
입력:
입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.
출력:
티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.
풀이:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, k = map(int,sys.stdin.readline().split())
lst = list(map(int,sys.stdin.readline().split()))
be = [lst[i] - lst[i-1] for i in range(1,len(lst))]
be.sort()
print(sum(be[:n-k]))
가장 중요한 부분은 마지막 sum으로 뽑아 내는 부분이다.
문제 예시를 들어보자
5 3
1 3 5 6 10
1 (2) 3 (2) 5 (1) 6 (4) 10
괄호는 인접한 숫자의 차이를 나타낸다. 그것을 be에 담고 오름차순을 해준다
be = [1,2,2,4]
인접한 수의 차이가 크면 같은 조에 들어 있으면 안된다는 것이다. 그렇게 되면 최선의 방법은 그 둘이 다른 조여야 한다.
610 이 붙는 상황에서 6 / 10 이렇게 따로 되어야 한다는것이다. 그러면 1356 10 이렇게 된다.
조를 나누기 위해서는 n-k 개를 해주면 되고, 사이 간격이 큰 값을 빼놓고 더해주면 정답이 된다
댓글