[백준 13164번] : 행복 유치원 파이썬 풀이
|
시간 제한
|
메모리 제한
|
제출
|
정답
|
맞힌 사람
|
정답 비율
|
|
1 초
|
512 MB
|
5886
|
3196
|
2605
|
55.320%
|
문제
행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.
이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.
입력
입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.
출력
티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.
예제 입력 1
|
5 3
1 3 5 6 10
|
예제 출력 1
|
3
|
문제를 풀기 위한 핵심 코드는 '인접한 사람들' 끼리 조를 이룬다는 점이다.
아래와 같이 사람이 6명 있다고 가정해보자. 편의를 위해 사람을 0으로 표현한다.
0,0,0,0,0,0
이 6명의 사람을 3개의 조로 나눈다고 생각해보면 다음과 같이 생각할 수 있다.
0/0,0/0,0,0
0,0/0,0/0,0
0/0,0,0,0/0
...
'인접한 사람들' 끼리 조를 나누는 것 이므로 입력받은 사람들 사이에 경계를 고른다고 생각하면 3개의 조로 나눌때는 2개의 경계를 고르면 된다는 것을 알 수 있다. 즉 k개의 조로 나누려면 사람들 사이를 가를 k-1개의 경계를 고르면 된다.
다음으로 가장 키가 큰 사람과 가장 키가 작은 사람의 키 차이를 어떻게 구할 지 생각해보자.
1,3,5,6와 같이 사람들이 서 있다고 할때,(각 숫자는 사람의 키를 의미한다.) 인접한 사람들 사이의 키 차이를 기록해 보면 2,2,1과 같이 표현 할 수 있다. 이 그룹에서 1,3의 키 차이는 2이고 3,5의 키 차이는 2이고, 5,6의 키 차이는 1이므로, 결국 키가 가장 작은사람(1)과 키가 가장 큰 사람(6)의 키 차이는 2+2+1 = 5 임을 알 수 있다.
이것을 앞서 말한 경계 설정과 함께 해석해보면, 인접한 사람들 사이의 값이 크면 그 값을 경계로 삼으면 된다는 힌트를 얻을 수 있다.
따라서 문제를 풀기 위해선 아래와 같은 순서를 따르면 된다.
1. 인접한 사람들 사이의 키 차이 배열을 만든다. (각 키 차이는 두 사람 사이의 '경계'가 된다.)
2. 키 차이 배열을 오름차순정렬 한 뒤, 가장 큰 k-1개의 경계를 고른다.
(각 조에서의 키 차이의 합이 최소가 되도록 하는것이 목표이므로, 가장 큰 k-1개를 경계로 삼으면 두 사람 사이의 키 차이는 무시할수 있다.)
=> 예를 들어 1,4,2,7,8,10 와 같이 있을때 인접한 키 차이 배열은 3,2,5,1,2 이 되고, 이 중에서 경계로 5와 3을 지정하면 1/4,2/7,8,10 으로 조가 나뉘게 된다.
3. 이후 k-1개의 값을 무시하고 나머지 값들을 더하면 이 값이 각 조의 최소비용의 합이 된다.
=> 각각의 키 차이는 0/2/3이 되어 합은 5가 된다.(1+2+2 = 5)
위 아이디어를 정리한 코드와 주석은 아래와 같다.
# https://www.acmicpc.net/problem/13164
'''
인접한 사람들끼리의 키의 합을 최소로 하기 위해선
조를 나눌 '경계'를 잘 설정해야함
6명을 3개의 조로 나누는 상황을 가정할때
0/0,0,0,0/0
0,0/0,0/0,0
0,0/0,0,0/0
등으로 나눌 수 있고, 이는 경계를 2개 골라야 함을 의미한다
=> n명을 k개의 조로 나누면 k-1만큼의 경계를 골라야 한다.
사람이 여러명 있을때 가장 큰사람과 가장 작은 사람의 키 차이는
인접한 사람의 키 차이를 더한 값과 같다
1,3,5 와 같이 있을때, 1,3의 차이는 2이고 3,5의 차이는 2이므로
1,3,5 그룹에서 가장 큰 사람과 가장 작은 사람의 키 차이는 4이다.
이를 이용해서 모든 인접한 사람들의 키 차이를 구해 저장한 배열을 만들고
오름차순으로 정렬한다.
6명의 경우 인접한 키 차이 배열은 5개의 인덱스를 갖게 될 것이고
3개의 그룹으로 나눈다고 할 때, 5개의 인덱스 중 2개의 인덱스는 경계 값으로 무시 될 수 있다.
1,4,2,7,8,10 와 같이 있을때 인접한 키 차이 배열은
3,2,5,1,2 이 되고, 이 중에서 경계로 5와 3을 지정하면
1/4,2/7,8,10 으로 조가 나뉘게 되고, 각각의 키 차이는 0/2/3이 되어 합은 5가 된다.
따라서 키 차이 배열 3,2,5,1,2를 오름차순 정렬한 뒤(1,2,2,3,5)
이 중에서 가장 큰 k-1개의 값들을 무시하고 더하면 최소값이 된다.(1+2+2 = 5)
'''
n,k = map(int,input().split())
# 키 배열
h = list(map(int,input().split()))
# 인접한 키 배열
array = []
for i in range(1,len(h)):
array.append(h[i]-h[i-1])
# 인접한 키 배열 오름차순 정렬
array.sort()
# 가장 큰 k-1개 무시하고 나머지 값들 합하여 출력
# n-1 - (k-1) = n-k
print(sum(array[:n-k]))