[210406][백준/BOJ] 15663번 N과 M (9) 15664번 N과 M (10) 15665번 N과 M (11) 15666번 N과 M (12)

문제

N과 M (9)
https://www.acmicpc.net/problem/15663

N과 M (10)
https://www.acmicpc.net/problem/15664

N과 M (11)
https://www.acmicpc.net/problem/15665

N과 M (12)
https://www.acmicpc.net/problem/15666

---

풀이

N과 M (1)을 푼 상태에서 응용을 하면 문제를 풀 수 있다.
수열을 만들 값들을 입력받으며 입력받은 값은 벡터에 저장하여 문제를 해결하였다.
이전 문제들과는 다르게 중복된 값이 들어올 수 있다.

1. N과 M (9)번은 중복된 값이 들어오며 이는 이전값을 저장해서 비교하는 방식으로 해결하면 된다.

2. N과 M (10)번은 시작점을 만들어주면 된다.

3. N과 M (11)번은 vis 함수를 제거해주면 된다.

4. N과 M (12)번은 vis 함수를 제거해주고 시작점을 만들어주면 된다.

코드

N과 M (9)

#include <bits/stdc++.h>
using namespace std;

int board[10];
bool vis[10];
int n, m, num;
vector<int> V;

void func(int index)
{
	if (index == m)
	{
		for (int i = 0; i < m; ++i)
			cout << board[i] << ' ';
		cout << '\n';
		return;
	}
	int before = 0;
	for (int i = 0; i < V.size(); ++i)
	{
		if (!vis[i] && before != V[i])
		{
			before = V[i];
			board[index] = V[i];
			vis[i] = 1;
			func(index + 1);
			vis[i] = 0;
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	while (n--)
	{
		cin >> num;
		V.push_back(num);
	}
	sort(V.begin(), V.end());

	func(0);
}

N과 M (10)

#include <bits/stdc++.h>
using namespace std;

int board[10];
bool vis[10];
int n, m, num;
vector<int> V;

void func(int index, int start)
{
	if (index == m)
	{
		for (int i = 0; i < m; ++i)
			cout << board[i] << ' ';
		cout << '\n';
		return;
	}
	int before = 0;
	for (int i = start; i < V.size(); ++i)
	{
		if (!vis[i] && before != V[i])
		{
			before = V[i];
			board[index] = V[i];
			vis[i] = 1;
			func(index + 1, i);
			vis[i] = 0;
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	while (n--)
	{
		cin >> num;
		V.push_back(num);
	}
	sort(V.begin(), V.end());

	func(0, 0);
}

N과 M (11)

#include <bits/stdc++.h>
using namespace std;

int board[10];
int n, m, num;
vector<int> V;

void func(int index)
{
	if (index == m)
	{
		for (int i = 0; i < m; ++i)
			cout << board[i] << ' ';
		cout << '\n';
		return;
	}
	int before = 0;
	for (int i = 0; i < V.size(); ++i)
	{
		if (before != V[i])
		{
			before = V[i];
			board[index] = V[i];
			func(index + 1);
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	while (n--)
	{
		cin >> num;
		V.push_back(num);
	}
	sort(V.begin(), V.end());

	func(0);
}

N과 M (12)

#include <bits/stdc++.h>
using namespace std;

int board[10];
int n, m, num;
vector<int> V;

void func(int index, int start)
{
	if (index == m)
	{
		for (int i = 0; i < m; ++i)
			cout << board[i] << ' ';
		cout << '\n';
		return;
	}
	int before = 0;
	for (int i = start; i < V.size(); ++i)
	{
		if (before != V[i])
		{
			before = V[i];
			board[index] = V[i];
			func(index + 1, i);
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	while (n--)
	{
		cin >> num;
		V.push_back(num);
	}
	sort(V.begin(), V.end());

	func(0, 0);
}