[BOJ - 15650] N과 M(2)

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

15650번: N과 M (2)

 

조합 문제입니다.

 

이전 게시물에서 말했다시피,

 

순열이란 서로 다른 n개에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 말합니다.

 

하지만 조합의 경우에는 어떨까요?

 

이미 중학교, 고등학교 과정에서 배웠던 것과 같습니다!

 

조합은, 서로 다른 n개에서 순서에 상관 없이 r개를 뽑는 경우의 수를 말합니다.

 

여기서 순서에 상관 없다는 것은 뽑힌 순서가 다르더라도 내용물(원소)만 같다면 같은 녀석들로 간주한다는 것입니다.

 

n = 4, r = 2의 경우를 예로 들어보겠습니다.

 

총 원소 갯수가 4개인 {1,2,3,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)

 

총 12가지가 나옵니다.

 

여기서, 조합의 경우를 뽑아봅시다.

 

앞서 말했듯이 조합은 서로 다른 n개에서 순서에 상관 없이 r개를 뽑는 경우의 수 입니다.

 

순서에 상관 없다는 것은 뽑힌 순서가 다르더라도 내용물만 같다면 같은 녀석들로 간주한다는 것입니다.

 

이 조건들을 고려했을 때 나오는 경우의 수는

 

(1,2), (1,3), (1,4)

(2,3), (2,4)

(3,4)

 

총 6가지 경우의 수가 나옵니다.

 

(1,2)와 (2,1)은 순서는 다르지만 내용물은 같습니다.

 

그렇기 때문에 순서에 상관 없이 내용물만 봤을 때 같은 녀석들이기 때문에 (1,2)만 남기고 (2,1)은 지운 것입니다.

 

나머지 경우들도 마찬가지로 적용되어 위와 같은 경우의 수가 나왔습니다.

 

여기서 다시 한 번 정리해볼까요?

 

순열이란?

-> 서로 다른 n개에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 말합니다.

 

조합이란?

-> 서로 다른 n개에서 순서에 상관없이 r개를 뽑는 경우의 수를 말합니다.

 

그럼 다시 문제로 돌아와서,

 

저는 이전 게시물(15649번 문제)과 마찬가지로 예시를 보고 조합인걸 알았습니다.

 

풀이 방법은

 

1. 입력을 받습니다.

 

2. vec이라는 벡터에 1부터 n까지의 수를 넣고

 

3. dfs와 백트래킹을 이용해 모든 조합의 경우를 구했습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<int> vec, sel;

void dfs(int node) {
	if (sel.size() == m) {

		for (int i = 0; i < sel.size(); i++) {
			printf("%d ", sel[i]);
		}
		printf("\n");

		return;
	}

	for (int i = node; i < vec.size(); i++) {
		sel.push_back(vec[i]);
		dfs(i + 1);
		sel.pop_back();
	}
}

int main(void) {

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++) {
		vec.push_back(i);
	}

	dfs(0);


	getchar();
	getchar();

	return 0;
}