취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3298번 문제인 WEDDING이다.
문제는 아래 링크를 확인하자.

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

두 인접한 사람들의 키의 차들의 총합이 가장 작아지게끔 Mirko의 가족 K명의 사이사이(맨 앞과 맨 뒤 포함)에 다른 N-K명을 적절히 집어넣는 문제이다.

Mirko의 가족의 키의 최댓값을 kmx, 최솟값을 kmn이라 하자. 이 때 Mirko의 가족이 아니고 키가 kmn과 kmx 사이인 사람은 인접한 두 가족의 키 사이에 들어가는 구간에 (순서에 맞춰) 들어가는 식으로 줄을 서야 함을 쉽게 관찰할 수 있다.

이 문제를 어렵게 하는 것은 Mirko의 가족이 아닌 사람 중 키가 kmx보다 크거나 kmn보다 작은 사람들을 넣는 과정이다. 단순하게 생각하면 키가 kmx인 Mirko의 가족 주변에 키가 kmx보다 큰 사람들을 적절한 순서로 넣고 키가 kmn인 Mirko의 가족 주변에 키가 kmn보다 작은 사람들을 적절한 순서로 넣으면 문제를 해결할 수 있어보인다. 하지만 이러한 방식의 배치로는 다음과 같은 케이스를 통과하지 못한다.

Mirko의 가족들: [1500, 1600, 1400, 1500]
추가로 들어갈 사람들: 1000, 2000

이와 같은 케이스에서는 키가 2000인 사람이 키가 1600인 사람의 주변에 들어가는 것 보다는 줄의 한쪽 끝에 서는 것이 이득임을 관찰할 수 있다. 키가 1000인 사람이 키가 1500인 사람의 주변에 들어가는 것 보다는 줄의 다른 한쪽 끝에 서는 것이 이득임 또한 관찰할 수 있다.

이와 같은 관찰을 포함하면, 키가 kmx보다 큰 사람들 또는 kmn보다 작은 사람들이 줄을 서야하는 위치의 경우들을 아래와 같이 7가지로 분류할 수 있다.

1) 키가 kmx보다 큰 사람들은 맨 왼쪽에, kmn보다 작은 사람들은 키가 kmn인 Mirko 가족 주변에

2) 키가 kmx보다 큰 사람들은 맨 왼쪽에, kmn보다 작은 사람들은 맨 오른쪽에

3) 키가 kmx보다 큰 사람들은 키가 kmx인 Mirko 가족 주변에, kmn보다 작은 사람들은 맨 왼쪽에

3) 키가 kmx보다 큰 사람들은 키가 kmx인 Mirko 가족 주변에, kmn보다 작은 사람들은 맨 오른쪽에

5) 키가 kmx보다 큰 사람들은 맨 오른쪽에, kmn보다 작은 사람들은 맨 왼쪽에

6) 키가 kmx보다 큰 사람들은 맨 오른쪽에, kmn보다 작은 사람들은 키가 kmn인 Mirko 가족 주변에

7) 키가 kmx보다 큰 사람들은 키가 kmx인 Mirko 가족 주변에, kmn보다 작은 사람들은 키가 kmn인 Mirko 가족 주변에

키가 kmx보다 큰 사람과 키가 kmn보다 작은 사람 모두를 왼쪽에 또는 모두를 오른쪽에 몰아넣을 경우는 존재하지 않음을 확인하자.

위의 각 경우별로 문제를 해결해주자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, K;
int arr[10002];
int lentosg[2201];
vector<int> sg[10002];

int kfirst, klast, kmx, kmn, nmx, nmn = 1000000007;
int total;

int mxL, mxM, mxR, mnL, mnM, mnR;

bool comp(int& x, int& y) {
	return arr[x] < arr[y];
}

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

	cin >> N >> K;

	cin >> arr[1];
	int old = arr[1];

	kmx = kmn = old;

	for (int id = 2; id <= K; id++) {
		int& cur = arr[id]; cin >> cur;
		kmx = max(kmx, cur), kmn = min(kmn, cur);
		total += abs(cur - old);

		if (old < cur) {
			for (int i = old; i <= cur; i++) lentosg[i] = id;
		}
		else {
			for (int i = cur; i <= old; i++) lentosg[i] = id;
		}
		old = cur;
	}
	kfirst = arr[1], klast = arr[K];

	for (int i = 1000; i < kmn; i++) lentosg[i] = 0;
	for (int i = kmx + 1; i < 2201; i++) lentosg[i] = 10001;

	for (int id = K + 1; id <= N; id++) {
		int& cur = arr[id]; cin >> cur;
		nmx = max(nmx, cur), nmn = min(nmn, cur);
		sg[lentosg[cur]].emplace_back(id);
	}

	if (nmx > kmx) mxL = nmx - kfirst, mxM = (nmx - kmx) * 2, mxR = nmx - klast;
	if (nmn < kmn) mnL = kfirst - nmn, mnM = (kmn - nmn) * 2, mnR = klast - nmn;

	if (mxL <= min(mxM, mxR) && mnM <= min(mnL, mnR)) {
		cout << total + mxL + mnM << '\n';

		sort(sg[10001].begin(), sg[10001].end(), comp);
		for (auto iter = sg[10001].rbegin(); iter != sg[10001].rend(); iter++) cout << *iter << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			if (id == lentosg[kmn]) {
				sort(sg[0].begin(), sg[0].end(), comp);
				for (auto& x : sg[0]) cout << x << '\n';
			}
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}
	}

	else if (mxL <= min(mxM, mxR) && mnR <= min(mnL, mnM)) {
		cout << total + mxL + mnR << '\n';

		sort(sg[10001].begin(), sg[10001].end(), comp);
		for (auto iter = sg[10001].rbegin(); iter != sg[10001].rend(); iter++) cout << *iter << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}

		sort(sg[0].begin(), sg[0].end(), comp);
		for (auto iter = sg[0].rbegin(); iter != sg[0].rend(); iter++) cout << *iter << '\n';
	}
	else if (mxM <= min(mxL, mxR) && mnL <= min(mnM, mnR)) {
		cout << total + mxM + mnL << '\n';

		sort(sg[0].begin(), sg[0].end(), comp);
		for (auto& x : sg[0]) cout << x << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			if (id == lentosg[kmx]) {
				sort(sg[10001].begin(), sg[10001].end(), comp);
				for (auto& x : sg[10001]) cout << x << '\n';
			}
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}
	}
	else if (mxM <= min(mxL, mxR) && mnR <= min(mnL, mnM)) {
		cout << total + mxM + mnR << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			if (id == lentosg[kmx]) {
				sort(sg[10001].begin(), sg[10001].end(), comp);
				for (auto& x : sg[10001]) cout << x << '\n';
			}
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}

		sort(sg[0].begin(), sg[0].end(), comp);
		for (auto iter = sg[0].rbegin(); iter != sg[0].rend(); iter++) cout << *iter << '\n';
	}
	else if (mxR <= min(mxL, mxM) && mnL <= min(mnM, mnR)) {
		cout << total + mxR + mnL << '\n';

		sort(sg[0].begin(), sg[0].end(), comp);
		for (auto& x : sg[0]) cout << x << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}
		sort(sg[10001].begin(), sg[10001].end(), comp);
		for (auto& x : sg[10001]) cout << x << '\n';
	}
	else if (mxR <= min(mxL, mxM) && mnM <= min(mnL, mnR)) {
		cout << total + mxR + mnM << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			if (id == lentosg[kmn]) {
				sort(sg[0].begin(), sg[0].end(), comp);
				for (auto& x : sg[0]) cout << x << '\n';
			}
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}
		sort(sg[10001].begin(), sg[10001].end(), comp);
		for (auto& x : sg[10001]) cout << x << '\n';
	}
	else {
		cout << total + mxM + mnM << '\n';

		cout << 1 << '\n';
		for (int id = 2; id <= K; id++) {
			if (id == lentosg[kmx]) {
				sort(sg[10001].begin(), sg[10001].end(), comp);
				for (auto& x : sg[10001]) cout << x << '\n';
			}
			if (id == lentosg[kmn]) {
				sort(sg[0].begin(), sg[0].end(), comp);
				for (auto& x : sg[0]) cout << x << '\n';
			}
			sort(sg[id].begin(), sg[id].end(), comp);
			if (arr[id - 1] < arr[id]) {
				for (auto iter = sg[id].begin(); iter != sg[id].end(); iter++) cout << *iter << '\n';
			}
			else {
				for (auto iter = sg[id].rbegin(); iter != sg[id].rend(); iter++) cout << *iter << '\n';
			}

			cout << id << '\n';
		}
	}
}