문제
참고
해당 문제는 N명의 유치원생들에 대해 모든 조의 단체 티셔츠 비용의 합이 최소가 되도록 K개의 조로 나눈 후, 최소 비용을 출력하는 문제이다.
문제를 읽고 가장 먼저 입력 크기를 통해 시간복잡도를 생각했다. 입력 N의 크기는 최대 3*10^5 이기 때문에, 최대 O(NlogN) 알고리즘으로 구현해야 한다.
처음에 생각한 접근법은 경우에 수를 활용해서 가능한 모든 조 나누기 경우를 고려하는 방법이었다.
예를 들면 5명에 대해 3개의 조를 나누는 경우, 각 조마다 (1, 1, 3), (1, 2, 2), (1, 3, 1) 등등 각 경우를 순회하는 방법이었다.
하지만 해당 방법은
1) N=5인 경우에나 경우가 6개여서 모든 경우에 대한 탐색을 편하게 생각할 수 있지, 임의의 N에 대한 모든 조 나누기 경우의 수가 얼마나 있는지 생각하지 못하는 것과
(사실 공식이 있는 것도 같은데 내가 부족해서 생각하지 못한듯..)
2) 각 조 나누기 경우를 탐색할 때마다 모든 유치원생들을 탐색하면서 전체 비용을 계산하기 때문에 최소 O(N^2) 이상의 알고리즘을 가진다는 것이었다.
하지만 O(NlogN) 알고리즘을 갖기 위해서는 모든 유치원생들을 1번씩만 탐색하는 알고리즘을 구현해야 한다고 생각했지만, 아무리 생각해도 해당 방법이 떠오르지 않았다...
결국 나의 부족함을 받아들이면서 구글링을 통해 다른 분들의 풀이법을 참고했다.
참고한 풀이법은 다음과 같다.
기본적으로 한번씩 조를 나누는 경우에 대해 일반화 하여 생각했다.
만약 i번째 학생과 i-1번째 학생 사이를 갈라서 A와 B라는 조를 만들었다면, 모든 조에 대한 단체 티셔츠 비용은 다음과 같이 계산된다.
1) 조가 나눠지기 전까지의 전체 티셔츠 비용은 모든 유치원생이 있는 조 하나밖에 없기 때문에, 다음과 같다.
cost = a[N-1] - a[0] (배열의 인덱스는 0~N-1 까지 사용)
2) 조가 나눠져서 A와 B라는 조로 나누어지면,
A조의 단체 티셔츠 비용은 a[i-1] - a[0], B조의 단체 티셔츠 비용은 a[N-1] - a[i] 이므로 전체 티셔츠 비용은 다음과 같다.
cost = a[N-1] - a[i] + a[i-1] - a[0]
= a[N-1] - a[0] - ( a[i] - a[i-1] )
위의 관계식을 통해 조가 한번씩 나눠질 때마다 전체 티셔츠 비용에서 ( a[i] - a[i-1] ) 만큼 감소하는 것을 확인할 수 있다.
따라서 문제에서 주어지는 입력을 받으면서, 동시에 인근 두 학생의 키 차이를 저장하는 배열을 하나 선언하는 것이 이번 문제의 핵심 아이디어이다.
이후, 인근 두 학생의 키 차이를 저장한 배열을 정렬한 다음,
가장 큰 값부터 K-1개를 a[N-1] - a[0] 에서 빼주면 N명의 유치원생을 K개 조로 나누었을때 전체 티셔츠 비용의 최소값을 구할 수 있다.
풀이법을 보고 든 생각은 이전까지 푼 그리디 유형 문제와는 달리, 수학적인 아이디어(부분합?)이 많이 핵심인 문제라고 생각이 되었다.
다음에는 문제를 푸는 과정에서 특히, O(N^2) 미만의 시간복잡도를 만족하는 알고리즘을 떠올릴 때 부디 부분합과 같은 수학적인 접근법이 생각날 수 있으면 좋겠다...
해당 내용을 정리한 전체 코드는 다음과 같다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
//freopen("input.txt", "rt", stdin);
int n, k, temp, res;
vector<int> height, diff;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> temp;
height.push_back(temp);
if (i >= 1) {
diff.push_back(height[i] - height[i - 1]);
}
}
sort(diff.begin(), diff.end());
res = height[n - 1] - height[0];
for (int i = 0; i < k - 1; i++) {
res -= diff[n - 2 - i];
}
cout << res << "\n";
return 0;
}