[BOJ - 15652] N과 M(4)

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

15652번: N과 M (4)

 

중복 조합 문제 입니다.

 

중복 조합이란?

 

-> 서로 다른 n개에서 r개를 순서에 상관 없이 뽑는데 중복을 허용해서 뽑는 경우의 수를 말합니다.

 

쉽게 예로 들어보겠습니다.

 

n = 4, r = 2이고 모집합이 {1,2,3,4}일 때 순서에 상관 없이 중복을 허용해서 뽑는 경우의 수를 찾아본다면

 

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

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

(3,3), (3,4)

(4,4)

 

이렇게 나옵니다.

 

순서에 상관 없이(원소가 같은 녀석들은 하나로 포함한다는 뜻) 중복을 허용해서(모집합에서 뽑는 녀석들은 중복이 가능하다는 뜻) 뽑는 것이 바로 중복 조합입니다.

 

그럼 본론으로 들어가서,

 

문제를 풀 때 저는 이전의 N과 M 시리즈들과 마찬가지로 예시를 보고 중복 조합인 것을 파악하고 풀었습니다.

 

풀이 방법은

 

1. 입력을 받습니다.

 

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

 

3. dfs와 백트래킹을 이용해 풀었습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>

using namespace std;

int n, m;
vector<int> vec, sel;
map<string, int> dict;

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);
		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;
}