[그리디 #13] BOJ 13164 - 행복 유치원

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

13164번: 행복 유치원

 

1차 시도

예제를 토대로 알고리즘을 설계했다.

 

1. 가장 큰 것을 하나로 만듬

2. 두 개씩 묶는 것이 무조건 이득

 

위 알고리즘에는 크나큰 실수가 있다.

 

5 2

1 5 6 7 8

 

라는 반례가 존재한다.

 

조의 개수 K가 커지면 위의 알고리즘이 성립하지만, K가 적은 수일 경우 적용되지 않을  수 있다.

 

{ 1 } , { 5 6 7 8 } -> 정답: 4

{ 1 5 6 7 } , { 8 } -> 오답: 5

 

 

2차 시도

그러면 앞 뒤 수의 차이를 이용해서 묶어버리면 좋을 것 같다고 생각.

따라서, gap vector을 만들어 차이를 저장하고, 오름차순으로 정렬한다.

 

차이가 적은 수를 두 개씩 묶어서 사용한다.

 

그리고, 규칙이 존재했다.

1명 초과인 조의 경우, 여러 명있는 조는  최대 N-K개 이어야 한다. (우연히 발견!)

 

 

위 과정도 큰 실수가 존재한다.

바로, 무조건 2개씩 짝지어야 한다는 것.

2개 이상 짝지어야하는 경우를 생각하지 못했다.

 

그래서 2차시도에선 bool chk[N]을 사용해서 한번 묶인 NUM은 사용하지 않도록 해버렸다...

 

정답

3개이상 묶이는 경우도 생각해주었다.

 

1차 시도와 같은 예제를 사용해보자.

 

N = 5, K = 2

NUM: 1    5    6    7    8

GAP:     4    1    1     1 

 

GAP을 오른차순으로 정렬하면

5 6 7 8 1

 

N-K = 3이므로, 1명 초과 조가 최대 3개이어야 한다.

 

i < n-k를 돌면서 gap[i]를 sum에 더해주면 조가 묶이게 된다.

 

따라서, { 5 6 7 8 }, { 1 } 이 된다. 

sum은 3이 된다.

 

사용한 예제

5 3 1 2 2 2 2 ans : 0 6 4 1 3 5 6 10 11

 

 

추후 공부 방향

이번 문제처럼 점화식(?) 사용되는 문제도 있나보다 ㄷㄷㄷ

n-k를 찾는 것에서 DP의 느낌도 살짝 있는거 같다...

틀린 내용은 댓글로 부탁드립니다..

 

 

코드

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

using namespace std;

int n, k;
vector<long long > num;
// 차이, 시작idx
vector<pair<long long, int>> gap;
bool chk[300001];

void calcGap() {
	for (int i = 0; i < n - 1; i++) {
		gap.push_back({ num[i + 1] - num[i], i });
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		long long  tmp;
		cin >> tmp;
		num.push_back(tmp);
	}

	calcGap();
	sort(gap.begin(), gap.end());

	long long sum = 0;
	int cnt = 0;
	for (int i = 0; i < gap.size() && i < n - k; i++) {
		sum += gap[i].first;
	}

	cout << sum;
}

gap이 pair인 이유는 어느 위치의 차이인지 구별하기 위해 구현했는데

해당 코드에선 사용되지 않음