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

 

1) 문제설명

백준 Online Judge 15650번 N과 M (2)

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

15650번: N과 M (2)

 

2) 아이디어

기존 n과 m (1)에서 풀었던 백트래킹을 이용한다.

단 이번에는 중복을 허용하지 않기 때문에 dfs를 돌 때 1부터 순회하는 것이 아닌 그다음수부터 순회하면 중복이 사라진다

ex ) 순회하다가 (2 1 x) , (2 2 x)을 순회하는 것이 아닌 2의 다음수인 (2 3 x) 순으로 순회한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

int visited[10];
int temp[10][10];
int arr[10];
int m, n;

void dfs(int k, int x) {
	if (k == m ) {
		
		for (int i = 0; i < m; i++) {
			printf("%d ", arr[i]);
		}
		printf("\n");
		return;
	}

	for (int i = x; i <= n; i++) { // 1 ~ 4
		if (visited[i] == 0) {
			arr[k] = i; // arr[0] = 1
			visited[i] = 1;

			dfs(k + 1, i + 1); // k+1 == m 이 되면 출력하고 리턴
			visited[i] = 0;
		}
		
	}
}

int main() {
	cin >> n >> m; // 4 2
	dfs(0,1);

}