[백준] N과 M (1) ~ (12) 문제 풀이 및 조건 정리 C++

 

백준

15649번 N과 M (1), 15650번 N과 M (2) 문제, 15651번 N과 M (3) 문제, 15652번 N과 M (4) 문제

15654번 N과 M (5) 문제, 15655번 N과 M (6) 문제, 15656번 N과 M (7) 문제, 15657번 N과 M (8) 문제

15663번 N과 M (9) 문제, 15664번 N과 M (10) 문제, 15665번 N과 M (11) 문제, 15666번 N과 M (12) 문제

를 모두 모아 정리하며 C++ 해설을 제공합니다.

N과 M 문제는 위의 순서대로 유형이 존재하며 문제에 따라 일정한 조건을 조합하면 모두 해결할 수 있는 문제입니다.

 

모든 N과 M 문제는 공통적으로 백트래킹을 이용한 문제입니다.

백트래킹 알고리즘에 대한 개념을 적용하기 쉬운 문제들로 구성되었습니다.

 

15649번: N과 M (1)

#include <iostream>

using namespace std;

void dfs(int n, int m, int visited[], int arr[], int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (visited[i] == 0)
		{
			arr[cnt] = i;
			visited[i] = 1;
			dfs(n, m, visited, arr, cnt + 1);
			visited[i] = 0;
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;
	int arr[9] = { 0 };
	int visited[9] = { 0 };

	dfs(N, M, visited, arr, 0);
}

 

 

15650번: N과 M(2)

이 문제는 중복을 허용하지 않는 오름차순 배열을 출력하는 문제입니다.

 

 

#include <iostream>

using namespace std;

void dfs(int n, int m, int visited[], int arr[], int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (visited[i] == 0 && arr[cnt-1] < i)
		{
			visited[i] = 1;
			arr[cnt] = i;
			dfs(n, m, visited, arr, cnt + 1);
			visited[i] = 0;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;
	int visited[9] = { 0 };
	int arr[9] = { 0 };
	dfs(N, M, visited, arr, 0);
}

 

15651번: N과 M (3)

이 문제는 중복을 허용하는 오름차순 배열을 출력하는 문제입니다.

위의 문제들과 달리 백트래킹의 조건 필요 없이 출력을 하면 됩니다.

 

#include <iostream>

using namespace std;

void dfs(int n, int m, int visited[], int arr[], int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		arr[cnt] = i;
		dfs(n, m, visited, arr, cnt + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;
	int visited[9] = { 0 };
	int arr[9] = { 0 };
	dfs(N, M, visited, arr, 0);
}

 

15652번: N과 M (4)

 

해당 문제는 오름차순으로 같은 수를 여러 번 골라도 되지만, 똑같은 조합의 배열을 걸러내는 문제입니다.

저 같은 경우 dfs에서 추가 조건을 같은 조합의 배열이 있는지 확인하는 것이 아니라 이전 배열의 수보다 크거나 같은 숫자가 들어올 수 있도록 처리했습니다.

		if (i >= arr[cnt-1])
		{
			arr[cnt] = i;
			dfs(n, m, visited, arr, cnt + 1);
		}

#include <iostream>

using namespace std;

void dfs(int n, int m, int visited[], int arr[], int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		if (i >= arr[cnt-1])
		{
			arr[cnt] = i;
			dfs(n, m, visited, arr, cnt + 1);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;
	int visited[9] = { 0 };
	int arr[9] = { 0 };
	dfs(N, M, visited, arr, 0);
}

 

 

15654번: N과 M (5)

 

 

 

기존 N과 M 문제들은 1~N까지의 수를 기준으로 했으나 이번 문제는 제공되는 숫자들을 뽑아서 진행한다.

사실 크게 다를 것 없이 뽑는 숫자의 배열을 새로 만들어서 해당 배열에서 숫자를 뽑아 출력해주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(int n, int m, int visited[], int arr[], vector<int> v, int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i=1; i<=n; i++)
	{
		if (visited[i] == 0)
		{
			arr[cnt] = v[i-1];
			visited[i] = 1;
			dfs(n, m, visited, arr, v, cnt + 1);
			visited[i] = 0;
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;

	vector<int> pool;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		pool.push_back(a);
	}
	sort(pool.begin(), pool.end());

	int visited[9] = { 0 };
	int arr[9] = { 0 };
	dfs(N, M, visited, arr, pool, 0);
}

 

 

15655번: N과 M (6)

 

이번 문제는 N과 M (5)에서 배열의 조합에 중복이 없게 하면 된다.

N과 M(2) 문제와 같은 원리를 적용해주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(int n, int m, int visited[], int arr[], vector<int> v, int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i=1; i<=n; i++)
	{
		if (v[i-1] > arr[cnt-1])
		{
			arr[cnt] = v[i-1];
			visited[i] = 1;
			dfs(n, m, visited, arr, v, cnt + 1);
			visited[i] = 0;
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;

	vector<int> pool;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		pool.push_back(a);
	}
	sort(pool.begin(), pool.end());

	int visited[9] = { 0 };
	int arr[9] = { 0 };
	dfs(N, M, visited, arr, pool, 0);
}

 

 

15656번: N과 M (7)

 

이번에도 N과 M (3) 문제처럼 조건 없이 모두 출력해주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(int n, int m, int visited[], int arr[], vector<int> v, int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i=1; i<=n; i++)
	{
		arr[cnt] = v[i - 1];
		visited[i] = 1;
		dfs(n, m, visited, arr, v, cnt + 1);
		visited[i] = 0;
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;

	vector<int> pool;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		pool.push_back(a);
	}
	sort(pool.begin(), pool.end());

	int visited[8] = { 0 };
	int arr[8] = { 0 };
	dfs(N, M, visited, arr, pool, 0);
}

 

15657번: N과 M (8)

 

이번 문제도 N과 M (4) 문제와 같은 원리를 적용합니다.

	for (int i=1; i<=n; i++)
	{
		if (v[i - 1] >= arr[cnt - 1])
		{
			arr[cnt] = v[i - 1];
			dfs(n, m, visited, arr, v, cnt + 1);
		}
	}

 

숫자를 넣기 전에, 배열의 이전 수보다 크거나 같은 수를 집어 넣습니다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(int n, int m, int visited[], int arr[], vector<int> v, int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i=1; i<=n; i++)
	{
		if (v[i - 1] >= arr[cnt - 1])
		{
			arr[cnt] = v[i - 1];
			dfs(n, m, visited, arr, v, cnt + 1);
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;

	vector<int> pool;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		pool.push_back(a);
	}
	sort(pool.begin(), pool.end());

	int visited[8] = { 0 };
	int arr[8] = { 0 };
	dfs(N, M, visited, arr, pool, 0);
}

 

 

15663번: N과 M (9)

 

이번 문제는

• N개의 자연수 중에서 M개를 고른 수열을 뽑는 것이다.

여기서 중요한 점은 중복은 허용하지 않지만, 같은 자연수가 존재하면 해당 자연수로 뽑은 수열은 출력해야 된다.

 

	int dup = 0;
	for (int i = 0; i < n; i++)
	{
		if (visited[i] == 0 && dup != v[i])
		{
			visited[i] = 1;
			arr[cnt] = v[i];
			dup = v[i];
			dfs(n, m, visited, arr, v, cnt + 1);
			visited[i] = 0;
		}
	}

 

여기서 중복을 걸러준 것은 이전에 출현한 숫자이냐를 확인한다.

즉 예제2처럼 1, 7, 9, 9 숫자를 줬으면 

첫번째 9(2번 인덱스)는 모든 배열을 출력하고 dup = 9로 남겨두고 다음 3번 인덱스를 진행한다.

3번 인덱스인 두번째 9는 dup = 9이기 때문에 아무런 배열을 출력하지 못함.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(int n, int m, int visited[], int arr[], vector<int> v, int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	int dup = 0;
	for (int i = 0; i < n; i++)
	{
		if (visited[i] == 0 && dup != v[i])
		{
			visited[i] = 1;
			arr[cnt] = v[i];
			dup = v[i];
			dfs(n, m, visited, arr, v, cnt + 1);
			visited[i] = 0;
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;

	vector<int> pool;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		pool.push_back(a);
	}
	sort(pool.begin(), pool.end());

	int visited[9] = { 0 };
	int arr[9] = { 0 };
	dfs(N, M, visited, arr, pool, 0);
}

15664번: N과 M (10)

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(int n, int m, int visited[], int arr[], vector<int> v, int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	int dup = 0;
	for (int i = 0; i < n; i++)
	{
		if (visited[i] == 0 && dup != v[i] && v[i] >= arr[cnt-1])
		{
			visited[i] = 1;
			arr[cnt] = v[i];
			dup = v[i];
			dfs(n, m, visited, arr, v, cnt + 1);
			visited[i] = 0;
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;

	vector<int> pool;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		pool.push_back(a);
	}
	sort(pool.begin(), pool.end());

	int visited[9] = { 0 };
	int arr[9] = { 0 };
	dfs(N, M, visited, arr, pool, 0);
}

 

15665번: N과 M (11)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(int n, int m, int visited[], int arr[], vector<int> v, int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	int dup = 0;
	for (int i = 0; i < n; i++)
	{
		if (dup != v[i])
		{
			visited[i] = 1;
			arr[cnt] = v[i];
			dup = v[i];
			dfs(n, m, visited, arr, v, cnt + 1);
			visited[i] = 0;
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;

	vector<int> pool;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		pool.push_back(a);
	}
	sort(pool.begin(), pool.end());

	int visited[9] = { 0 };
	int arr[9] = { 0 };
	dfs(N, M, visited, arr, pool, 0);
}

 

 

15666번: N과 M (12)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(int n, int m, int visited[], int arr[], vector<int> v, int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << arr[i] << " ";
		}
		cout << "\n";
		return;
	}

	int dup = 0;
	for (int i = 0; i < n; i++)
	{
		if (dup != v[i] && v[i] >= arr[cnt-1])
		{
			visited[i] = 1;
			arr[cnt] = v[i];
			dup = v[i];
			dfs(n, m, visited, arr, v, cnt + 1);
			visited[i] = 0;
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;

	vector<int> pool;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		pool.push_back(a);
	}
	sort(pool.begin(), pool.end());

	int visited[9] = { 0 };
	int arr[9] = { 0 };
	dfs(N, M, visited, arr, pool, 0);
}

 

---

 

N과 M 문제 총 정리

조건에 따라 백트래킹의 조건을 다르게 설정한다.

 

숫자 Pool에서 숫자를 뽑아내는 기준으로 조건들을 나열하면 다음과 같습니다.

// 1번 조건
v[i] >= arr[cnt-1] // 이전에 등장한 수보다 크거나 같은 경우

// 2번 조건
dup != v[i] // 이전에 등장한 수와 같을 때 중복된 배열을 출력하지 않을 때

// 3번 조건
visited[i] == 0 // 중복된 수는 등장X -> 이때, 같은 숫자가 제공될 경우는 추가 조건 처리 필요

 

총 3가지 조건이 존재하며 해당 조건들을 조합하면 N과 M 문제들을 해결할 수 있습니다.

 

 

참고 사이트

https://gguzunhee.tistory.com/entry/%EB%B0%B1%EC%A4%8015649%EB%B2%88-N%EA%B3%BC-M1-cc