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

백준 15650 문제(Problem)

백준 15650 문제

 

 

 

풀이(Solution)

이 문제는 15649번 N과 M (1) 문제와 매우 유사한 문제이다. 문제의 핵심 포인트는 1~N까지의 자연수를 고르는데 중복이 불가능하고, 중복 수열 또한 있어서는 안된다.

1~N까지의 자연수 선택 중복을 피하기 위해서 visited 배열을 사용하였고, 중복 수열을 피하기 위해선 func 함수에 pos 변수 인자를 받아주었다.

func 함수의 기저조건은 depth가 M일 때 즉, 조합이 M개가 선택되었을 때 arr 배열에 저장되어 있는 값들을 출력하도록 설정하였다.

또한, pos값을 받은 pos+1부터 반복문을 돌게 하여 수열의 중복을 피하도록 코드를 짜보았다. 

 

 

 

 

코드(Code)

#include<iostream>
#define MAX 9;
using namespace std;
int N, M, visited[9], arr[9];

void func(int pos, int depth) {
	if(depth == M) {
		for(int i=0; i<M; i++)
			cout << arr[i] << ' ';
		cout << '\n';
		return;
	}

	for(int i=pos+1; i<=N; i++) {
		visited[i]=1;
		arr[depth]=i;
		func(i, depth+1);
		visited[i]=0;
	}
}

int main() {
	cin >> N >> M;
	func(0, 0);
}