취미로 코딩하기

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

이번에 볼 문제는 백준 15508번 문제인 Xayahh-Rakann at Moloco (Easy)이다.
문제는 아래 링크를 확인하자.

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

15509번 문제에서 조건이 약해진 문제이다. 해당 글의 풀이를 참고하자.

위의 문제풀이에서 knapsack 대신 모든 조합의 경우의 수를 탐색해도 문제를 해결할 수 있을 것이다.

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

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

int visited[1001];
int uf[1001], cnt[1001];
int findf(int cur) {
	if (cur == uf[cur]) return cur;
	return uf[cur] = findf(uf[cur]);
}

vector<int> vec;
int dp[2001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M, K; cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) uf[i] = i;
	for (int i = 1; i <= N; i++) cnt[i] = 1;

	while (M--) {
		int x, y; cin >> x >> y;
		x = findf(x), y = findf(y);
		if (x == y) continue;
		uf[y] = x;
		cnt[x] += cnt[y];
	}

	for (int i = 1; i <= N; i++) {
		int ii = findf(i);
		if (visited[ii]) continue;
		visited[ii] = 1;
		vec.emplace_back(cnt[ii]);
	}

	dp[0] = 1;
	for (auto& x : vec) {
		for (int i = N; i > -1; i--) {
			if (dp[i]) dp[i + x] = 1;
		}
	}

	if (dp[K]) cout << "SAFE";
	else cout << "DOOMED";
}