[BOJ - 15649] N과 M(1)

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

15649번: N과 M (1)

 

 

순열 문제입니다.

 

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

 

여기서 순서에 상관있게 나열한다(?) 라는 것은 순서만 다르면 다른 녀석들로 구분한다는 것입니다.

 

예를 들어, {1,2,3,4} 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,1), (2,2) ... 등은 원소의 중복이니까 안됩니다!) 총 12가지를 뽑았습니다.

 

여기서 순서에 상관있게 나열한다는 것은 앞에서도 말했듯이 순서만 다르면 다른 녀석들로 구분하는 것입니다.

 

(1,2)와 (2,1)은 모집합의 같은 원소들로 이루어져 있지만 뽑은 순서는 다릅니다.

 

이렇게 뽑은 경우의 수를 순서에 상관있게 나열했다고 생각하시면 됩니다.

 

그럼 다시 문제로 돌아가보면

 

문제에서 딱히 순열이라고 알 수 있는 조건은 없습니다.

 

하지만 예시를 보시면 제가 위에 설명했던 내용의 입출력이 들어와 있음을 알 수 있습니다.

(저는 예시를 보고 순열 문제라고 생각하고 접근했습니다.)

 

이제 코드를 작성해보면

 

1. 입력을 받는다.

 

2. 1부터 n까지의 숫자를 vec이라는 벡터에 넣어줍니다.

 

3. dfs()와 백트래킹으로 m개의 원소를 선택하여 순열을 만들어줍니다.

 

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

using namespace std;

int n, m;
int visited[9];
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++) {
		if (visited[i] == 0) {
			visited[i] = 1;
			sel.push_back(vec[i]);
			dfs(i + 1);
			visited[i] = 0;
			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;
}