[C++ 백준] 15650 N과 M (2)

블로그에 올리는 모든 문제 풀이는 깃허브에 올려져 있습니다.

---

문제 설명

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
  1. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 (1 <=M <=N <=8)
  2. 오름차순

---

풀이 전략

• dfs를 활용한 조합 문제이다.
• for문의 i값을 재귀 함수의 인자로 넘겨주면 앞에서 이미 찾은 조합은 다시 뽑지 않도록 만들 수 있다.
• 중복이 없으므로 뒤의 숫자는 무조건 앞의 숫자보다 크다.

소스 코드

#include <iostream>

int arr[9] = { 0, };
bool visited[9] = { false, };

using namespace std;
void Dfs( int num, int cnt, int n, int m )
{
	if( cnt == m )
	{
		for (int i = 0; i < m; i++)
			cout << arr[i] << ' ';

		cout << '\n';
		return;
	}

	for (int i = num; i <= n; i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			arr[cnt] = i;
			Dfs(i + 1, cnt + 1, n, m);
			visited[i] = false;
		}
	}
}

int main()
{
	int n, m;
	cin >> n >> m;
	Dfs(1, 0, n, m);
}

---

링크

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

15650번: N과 M (2)