[BAEKJOON] 13164 행복 유치원 (C++)

https://www.acmicpc.net/problem/13164

13164번: 행복 유치원

문제

원생의 수만큼 원생의 키가 주어진다.

N명의 원생들을 K개의 그룹으로 만드는데, 그룹내에서 가장 큰 원생과 작은 원생의 키차이만큼 비용이 발생한다.

1명의 원생으로 이루어진 경우는 비용이 0이다. (자기자신 - 자기자신 = 0)

비용을 최소로 만드는 경우의 비용을 구하는 문제

 

접근

그룹은 많이 많들 수 있을 수록 이득이다. 만약 N명의 원생에 대하여 N개의 그룹을 구성할 수 있다면 총 비용은 0이다.

그럼 최악은? 1개의 그룹인 경우이다. 이 경우 배열의 맨 처음과 끝 값의 차만큼 비용이 발생한다.

최악의 상태에서 그룹을 만들어가면서 비용을 줄이는 것이 접근방법이다.

 

그룹을 만든다는 것은 두 원생사이의 접점을 끊는다고 생각하면 직관적이다. (원생은 키순서대로 주어진다)

접점을 끊으면 두 원생사이의 키차이만큼 비용이 감소한다.

그럼 이제 결정할 것은 어떤 원생사이의 접점을 끊을 것인가이다. -> 가장 차이가 큰 원생 사이의 접점부터 차례로 K-1개를 끊어주면 된다. (K개의 그룹을 구성하기 위해서는 K-1개의 구분점이 필요한다)

따라서 각 원생사이의 차이를 모두 vector에 넣고, 큰 것부터 차례로 K-1개 확인해서 초기 최대발생 비용에서 제외해주면 최소값을 구할 수 있다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

#define endl "\n"

using namespace std;

int N, K, ans;
int height[300000];
vector<int> W;
void Input() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> height[i];
	}
}

void Solve() {
	for (int i = 1; i<N; i++) {
		ans += height[i] - height[i - 1];
		W.push_back(height[i] - height[i - 1]);
	}
	sort(W.begin(), W.end(), greater<int>());
	for (int i = 0; i < K - 1; i++) {
		ans -= W[i];
	}
	cout << ans;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "r", stdin);
	Input();
	Solve();


	return 0;
}

 

그리디는 방법만 생각하면 코드는 간단하게 짤 수 있는 것 같다.