[BOJ - 15651] N과 M(3)

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

15651번: N과 M (3)

 

중복순열 문제입니다.

 

중복순열이란?

 

순열인데 중복의 경우도 고려하는 순열입니다.

 

다시 말하자면,

 

서로 다른 n개에서 r개를 중복을 허용하여 순서에 상관있게 나열하는 것을 말합니다!

 

바로 예로 들어보겠습니다.

 

n = 4, r = 2이고 모집합이 {1,2,3,4}인 경우를 고려해봅시다.

 

원래 순열이라면

 

(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,1), (1,2), (1,3), (1,4)

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

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

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

 

다른 N과 M 시리즈의 문제들과 마찬가지로 저는 예시를 보고 중복순열이란 것을 알았고 문제를 풀었습니다.

 

풀이 방법은 다음과 같습니다.

 

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() {
	if (sel.size() == m) {

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

		return;
	}

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

//중복순열 문제
int main(void) {

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

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

	dfs();

	getchar();
	getchar();

	return 0;
}