[BOJ] 백준 3088. 화분 부수기 (Gold V)

쉬울 줄 알았는데 생각보다 헤맨 문제.

관찰의 중요성을 일깨워주는 문제이다.

문제는 아래와 같다.

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

3088번: 화분 부수기

주의할 점은 인접한 오른쪽 화분만 깨뜨리는 것이 아닌, 오른쪽에 있는 화분들 중 숫자가 하나라도 겹치는 화분들은 모조리 깨뜨리는 것이다.

문제를 잘못 읽지 않도록 주의하자.

---

의식의 흐름 및 해설

처음에는 문제를 잘못 읽어서 인접한 화분만 비교하여 유니온파인드로 같은 숫자일 경우 merge해주어 풀었다.

근데 문제를 다시 읽은 후, 알고리즘 자체를 갈아치우고 다시 고민해봤다.

 

겹치는 개수가 최대한 많아야되므로 각 화분에 포함된 숫자의 개수를 세주려다가 O(N^2)이 예상돼 포기했다. 

결국 한번만 스위핑하는 방법이 있단 소리인데, 도저히 투포인터처럼 보이는 문제는 아니어서 문제를 다시 관찰했다.

 

그러다 관찰 후에 핵심 키포인트를 깨달았다.

 

1. 맨왼쪽 화분은 무조건 깨뜨려야한다. 그렇지 않으면 맨왼쪽 화분은 깨뜨릴 방법이 없다.

2. 오른쪽 방향에 있는 화분들만 깨진다.

 

맨왼쪽 화분과 겹치는 숫자를 하나라도 가진 오른쪽 화분들은 모조리 와장창 깨질것이므로,

왼쪽부터 스위핑하면서 아예 겹치지 않는 화분들만 깨뜨리면 된다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
const int MAX = 300011;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e18;
int N, cnt[1000001], ans;
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (!cnt[a] && !cnt[b] && !cnt[c])
			ans++;
		cnt[a]++;
		cnt[b]++;
		cnt[c]++;
	}
	cout << ans << "\n";
}

---

역시 문제는 관찰이 중요하다...

사람마다 난이도평가가 갈릴듯한 문제.