[C++] 백준 16457번: 단풍잎 이야기

문제 링크

16457번: 단풍잎 이야기

문제 요약

메이플스토리를 하는데, $2\times N$개의 스킬이 존재한다. 키보드의 키가 $N$개가 있고, 각 키에는 하나의 스킬을 매핑할 수 있다. $M$개의 퀘스트가 있고, 각 퀘스트에서는 $K$개의 스킬을 써야 한다. 키와 스킬을 매핑시켜서 최대로 참여 가능한 퀘스트 수를 구해야 한다.

접근 방법

N과 M 시리즈와 비슷한 난이도의 문제입니다.

N이 10밖에 되지 않기 때문에 브루트포스 알고리즘으로 풀립니다. 2 * N개의 스킬 중에 N개를 뽑는 모든 경우의 수를 따져보고, 참여할 수 있는 퀘스트를 일일이 파악해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, m, k, ans;
vector<int> route;

void func(vector<vector<int>>& v, int idx, int cnt) {
	if (cnt == n) {
		int c = 0;
		for (auto& i : v) {
			bool flag = true;
			for (auto& j : i) {
				if (!binary_search(route.begin(), route.end(), j)) {
					flag = false;
					break;
				}
			}

			if (flag)
				c++;
		}

		ans = max(ans, c);
		return;
	}

	for (int i = idx; i <= 2 * n; i++) {
		route.push_back(i);
		func(v, i + 1, cnt + 1);
		route.pop_back();
	}
}

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

	
	cin >> n >> m >> k;
	vector<vector<int>> v(m, vector<int>(k));
	for (int i = 0; i < m; i++)
		for (int j = 0; j < k; j++)
			cin >> v[i][j];

	func(v, 1, 0);
	cout << ans << '\n';
	return 0;
}