[백준 15650] N과 M (2) #조합

# 문제 링크 

www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

 

이 문제는 1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열을 출력하는 문제로, 조합 문제입니다. 

이전 글인 순열 계산 문제에서 4개 중에 2개를 꼽으면 아래와 같습니다.

 

(순열 계산 참고)

2021.03.13 - [Computer Science&Engineering/코딩테스트] - [백준 15649] N과 M (1))

 

 

4 2

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

 

여기서 (1, 2)와 (2, 1) 이 중복되어 나옵니다. (1, 3)과 (3, 1)도 마찬가지. (2, 3) 과 (3, 2)도 마찬가지...

이 때, 다음 수로 자기 자신보다 큰 수를 출력해주면 중복이 없이 계산이 됩니다. 따라서 DFS 에 시작값을 전해주어 이전 값보다 1 큰 수부터 출력하도록 해줍니다.

 

 

# 제출 코드

 

// N과 M(2) 
# include <iostream>
using namespace std;

int N, M;
int num[10];

void DFS(int node, int start){
	if (node >= M) {
		for(int i = 0; i < M; i++){
			cout << num[i] << ' ';
		}
		cout << '\n';
		return;
	}
	for(int i = start ; i<=N; i++){
		num[node] = i;
		DFS(node + 1, i + 1);
	}
}

int main() {	
	cin >> N >> M;
	DFS(0, 1);
	return 0;
}