[210406][백준/BOJ] 15650번 N과 M (2) 15651번 N과 M (3) 15652번 N과 M (4)

문제

N과 M (2)
https://www.acmicpc.net/problem/15650

N과 M (3)
https://www.acmicpc.net/problem/15651

N과 M (4)
https://www.acmicpc.net/problem/15652

---

풀이

N과 M (1)을 푼 상태에서 응용을 하면 문제를 풀 수 있다.

1. N과 M (2)번은 이미 방문한 수는 출력하지 않으면서 자신보다 큰 수를 출력하는 문제이다. 이는 시작점을 만들어서 해결할 수 있다.

2. N과 M (3)번은 이미 방문했더라도 이를 신경쓰지 않고 모든 경우의 수를 출력하는 문제이다. 따라서 vis 함수를 통해 방문했는지 여부를 확인하였는데 이를 제거해주면 된다

3. N과 M (4)번은 N과 M (3)번에서 자신보다 큰 수를 출력하는 문제이다. 따라서 vis함수를 제거하고 시작점을 만들어서 이를 해결할 수 있다.

코드

N과 M (2)

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

int board[10];
bool vis[10];
int n, m;

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

	cin >> n >> m;

	func(0, 1);
}

N과 M (3)

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

int board[10];
int n, m;

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

	cin >> n >> m;

	func(0);
}

N과 M (4)

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

int board[10];
int n, m;

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

	cin >> n >> m;

	func(0, 1);
}