[BOJ/Python] 13164번 문제풀이

문제 설명

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

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

입력

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

출력

티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

---

풀이 과정

본격적인 풀이 과정을 살펴보기에 앞서, 해당 문제에서 핵심이 되는 그리디 알고리즘에 대해 알아보자

그리디 알고리즘

탐욕법이라고도 하는 그리디(Greedy) 알고리즘은 “현재 상황에서 최적이라고 생각하는 해를 선택“하는 방법이다.
그러나 말그대로 앞으로 남은 선택들을 고려하지 않고 현재 상황만 고려하기 때문에 항상 최적해(Global optimum)를 보장하지는 않는다.

 

예를 들어, 아래 그림과 같은 트리구조의 경로가 있고 우리는 경로마다 놓여있는 돈을 얻을 수 있다고 해보자.

제일 많은 돈을 얻기 위해서는 빨간색 경로로 이동해야 하지만, 눈 앞에 놓인 갈림길에서 높은 금액만을 선택하는 그리디 방법은 파란색 경로로 이동한다. 따라서 $50 밖에 얻지 못한다.

 

이 외에도 그리디 알고리즘에 대한 추가적인 설명은 아래 링크에서 확인할 수 있다.

▶ 그리디 알고리즘 참고자료

 

코드 작성

코드 작성 및 풀이 과정은 아래와 같다.

1. 유치원 학생의 수(N)과 나누려고 하는 조의 개수(K)를 입력받기
2. 원생들의 키(h)를 입력받아 리스트에 저장
3. N-1번만큼의 반복문을 돌려 인접한 원소들의 차이를 계산해서 리스트 arr에 추가해주기
4. 최솟값을 찾기 위해 arr를 오름차순으로 정렬
5. N명의 사람을 K개의 조로 나누었으므로 N-K까지의 키 차이를 더하면 값을 얻을 수 있음

N,K = map(int, input().split())
h = list(map(int, input().split()))
 
arr = []
 
for i in range(N-1):
    a = h[i+1] - h[i]
    arr.append(a)
 
arr.sort()
cost_result = 0
 
for i in range(N-K):
    cost_result += arr[i]
 
print(cost_result)

 

어찌저찌 문제를 풀기는 했지만 아직도 알고리즘은 어렵따...

공부 열심히 해야지...