[BOJ 32760 // C++] Nothing Everything

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

 

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

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

 

\(i\)번 정점에서 E 연산을 수행하면 \(i\)보다 작은 번호를 가진 정점과 \(i\)를 잇는 모든 간선이 추가되고, N 연산을 수행하면 이러한 모든 간선이 추가되지 않음을 관찰하자.

 

따라서, 각 정점마다 그 정점보다 작은 번호로 이어진 간선이 총 몇 개 존재하는지 세어 각각 N 또는 E 연산으로 해당 에지들을 추가할 수 있는지 판단하는 것으로 문제를 해결할 수 있다.

 

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

#include <iostream>
#include <string>
using namespace std;

int N, M;
int cnt[100001];
string ans;

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

	cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		if (x > y) cnt[x]++;
		else cnt[y]++;
	}

	for (int i = 2; i <= N; i++) {
		if (!cnt[i]) ans += 'N';
		else if (cnt[i] == i - 1) ans += 'E';
		else {
			cout << -1;
			return 0;
		}
	}
	cout << ans;
}