[BOJ] 18859 - 부모님께 큰절 하고

[백준] 18859 - 부모님께 큰절 하고

아이디어

주어진 문제는 n개의 수를 2개의 등차수열로 나누는 것이다. 이것은 다음과 같이 표현할 수 있다.
“n개의 수 중 일부 숫자를 뽑아 1개의 등차 수열을 만들었을 때, 나머지 숫자들이 등차수열을 이루게 할 수 있는가?”
따라서 우리는 n개의 수에서 1개의 등차 수열을 만들고 나머지 수가 등차수열을 이룰 수 있는지를 확인하면 된다.
이 때 중요한 조건이 2가지 있다.

1. 만들어내는 두 개의 등차 수열은 가장 작은 숫자 1개를 공유한다.
2. 두 개의 등차수열은 모두 공차가 0이 될 수 없으며, 2개 이상의 원소를 필요로 한다.

과제로 풀었던 문제와 핵심으로 다른 조건이 위의 두가지였는데.. 여기서 달라지는 예외처리를 미처 파악하지 못해서 많은 틀렸습니다를 받았다.(눈물)

구현

자, 이제 숫자를 하나씩 제거하며 나머지 숫자가 등차수열을 이루는지 확인해보자.(나머지 숫자의 공차 또한 가장 작은 수와 남은 수 중 가장 작은 수와의 차이이다.)
완전탐색으로 문제를 해결할 경우, 매 확인마다 $O(n)$의 시간을 필요로 한다. 기껏 확인하는 횟수를 줄였는데 $O(n^2)$의 시간복잡도가 나온다.
우리에게는 우리의 친구 map과 set이 있다는 사실을 잊지 말자.
주어진 수열을 정렬하고, 인접한 두 숫자간의 차이를 모두 map에 저장해주었다.(multiset을 이용해도 된다.)
중복된 공차가 존재할 수도 있으므로 diff[공차]=갯수와 같은 형태로 저장하는 것을 잊지 마시라.
숫자를 제거할 때는 사라지는 공차와 생성되는 공차를 모두 반영해주어야 한다.
이는 삭제하는 원소의 왼쪽과 오른쪽 원소가 존재함에 따라 달라진다.
만일 1 3 5 -> 1 5로 3을 제거해 수열이 변경되었다면, 1과 3의 차이 2, 3과 5의 차이 2가 사라지고 1과 5의 차이 4가 새로이 생겨난다.

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> v;
map<ll, ll> diffs;
set<ll> indexs;

int main(void) {
	ll n;
	scanf("%lld", &n);

	if (n == 3) {
		printf("Yes\n");
		return 0;
	}

	for (ll i = 0; i < n; i++) {
		ll x;
		scanf("%lld", &x);
		v.push_back(x);
		indexs.insert(i);
	}
	sort(v.begin(), v.end());

	for (ll i = 1; i < n; i++) {
		diffs[v[i] - v[i - 1]]++;
	}

	ll diff = v[1] - v[0], last = 1, prev = 2, fst = -1;
	bool br = true;

	if (diff == 0) {
		printf("No\n");
		return 0;
	}

	diffs[diff]--;
	if (diffs[diff] == 0) {
		diffs.erase(diffs.find(diff));
	}
	
	diffs[v[2] - v[1]]--;
	if (diffs[v[2] - v[1]] == 0) {
		diffs.erase(diffs.find(v[2] - v[1]));
	}
	indexs.erase(indexs.find(0));

	while (!diffs.empty()) {
		indexs.erase(indexs.find(last));

		if ((diffs.size() == 1) && (diffs.begin()->first != 0) && (diffs.begin()->first == v[*indexs.begin()] - v[0])) {
			break;
		}

		auto it = lower_bound(v.begin() + last + 1, v.end(), v[last] + diff);
		if (it == v.end() || (*it != v[last] + diff)) {
			printf("No\n");
			return 0;
		}
		ll next = it - v.begin();
		auto L = indexs.lower_bound(next);
		if (next != *indexs.begin()) {
			L--;
			diffs[v[next] - v[*L]]--;
			if (diffs[v[next] - v[*L]] == 0)
				diffs.erase(diffs.find(v[next] - v[*L]));
		}
		if (next + 1 < n) {
			diffs[v[next + 1] - v[next]]--;
			if (diffs[v[next + 1] - v[next]] == 0)
				diffs.erase(diffs.find(v[next + 1] - v[next]));
		}
		if ((next != *indexs.begin()) && ((next + 1) < n)) {
			diffs[v[next + 1] - v[*L]]++;
		}
		last = next;
	}
	if (v[*indexs.begin()] - v[0] != 0)
		printf("Yes\n");
	else printf("No\n");
	return 0;
}