취미로 코딩하기

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

이번에 볼 문제는 백준 3088번 문제인 화분 부수기이다.
문제는 아래 링크를 확인하자.

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

뒤의 어떤 화분을 깨더라도 앞의 화분이 깨지지는 않는 다는 점에 착안하면, 무조건 화분을 앞에서부터 깨는 것이 이득임을 알 수 있다.

화분에 써있는 숫자는 100만 이하이므로, 크기 100만의 배열을 만들고 앞서서 해당 숫자가 적힌 화분이 있었는지 확인하는 것으로 문제를 빠르게 해결할 수 있다.

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

#include <iostream>
using namespace std;

bool chk[1000001];

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

	int N; cin >> N;
	int cnt = 0;
	while (N--) {
		int x, y, z; cin >> x >> y >> z;
		if (!(chk[x] || chk[y] || chk[z])) cnt++;
		chk[x] = chk[y] = chk[z] = 1;
	}
	cout << cnt;
}