백트래킹 - 백준 15649번 N과 M (1) ~ (4)

순열, 조합에 대한 더 자세한 설명은 👉 DFS로 순열 및 조합 구현 ( blahblahlab.tistory.com/28 )

(1) 순열

N개 중에 중복없이 M개를 고른다 & 수열사이 대소관계는 없다 (오름차순 혹은 내림차순)

👉 nPm 순열을 얘기하는거다

중복이 없어야 하므로 VISITED 배열을 이용해 방문여부를 따져야한다. 

또 오름차순 내림차순과 같은 관계가 없으므로 항상 1부터 시작해도 된다. 

N을 입력받으면 1 ~ N 까지의 수로 순열을 만들면 되기 때문에 별다른 배열 없이 인덱스로만 구성하면 된다. 

#include <iostream>
#include <vector>
using namespace std;
int n, m;

vector<int>temp;
int visited[9] = { false };

void backtracking(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < temp.size(); i++) printf("%d ", temp[i]);
		printf("\n");
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (visited[i]) continue;
		visited[i] = true;
		temp.push_back(i);
		backtracking(cnt + 1);
		temp.pop_back();
		visited[i] = false;
	}
}

int main() {
	scanf("%d %d", &n, &m);
	backtracking(0);
}

www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

2) 조합

N개 중에 중복없이 M개를 고른다 & 수열은 오름차순이어야한다 

👉 nCm 조합을 얘기하는거다.

중복이 없어야 하므로 VISITED 배열을 이용해 방문여부를 따져야한다.

또 오름차순이어야하므로 만약 3을 뽑았다면 3보다 큰 숫자들이 뒤에 나와야한다. 그렇기 때문에 시작하는 인덱스를 늘리며 계산해주어야한다. 

N을 입력받으면 1 ~ N 까지의 수로 순열을 만들면 되기 때문에 별다른 배열 없이 인덱스로만 구성하면 된다. 

#include <iostream>
#include <vector>
using namespace std;
int n, m;

vector<int>temp;
int visited[9] = { false };

void backtracking(int cnt , int idx) {
	if (cnt == m) {
		for (int i = 0; i < temp.size(); i++) printf("%d ", temp[i]);
		printf("\n");
		return;
	}
	for (int i = idx; i <= n; i++) {
		if (visited[i]) continue;
		visited[i] = true;
		temp.push_back(i);
		backtracking(cnt + 1 ,i+1);
		temp.pop_back();
		visited[i] = false;
	}
}

int main() {
	scanf("%d %d", &n, &m);
	backtracking(0 ,1);
}

www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

3) 중복순열 

같은 수를 여러번 골라도 된다 (중복가능) & 오름차순과 같은 관계가 없다 

👉 nPIm 중복순열을 얘기하는거다.

중복가능하므로 방문여부를 따질 필요 없다. 

또 오름차순 내림차순과 같은 관계가 없으므로 항상 1부터 시작해도 된다. 

N을 입력받으면 1 ~ N 까지의 수로 순열을 만들면 되기 때문에 별다른 배열 없이 인덱스로만 구성하면 된다. 

 

#include <iostream>
#include <vector>
using namespace std;
int n, m;

vector<int>temp;
int visited[9] = { false };

void backtracking(int cnt) {
	if (cnt == m) {
		for (int i = 0; i < temp.size(); i++) printf("%d ", temp[i]);
		printf("\n");
		return;
	}
	for (int i = 1; i <= n; i++) {
		temp.push_back(i);
		backtracking(cnt + 1);
		temp.pop_back();
	}
}

int main() {
	scanf("%d %d", &n, &m);
	backtracking(0);
}

www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

4) 중복조합 

같은 수를 여러번 골라도 된다 & 비내림차순 ( 같거나 점점 커진다 )

👉 nHm 중복조합을 얘기하는거다.

중복가능하므로 방문여부를 따질 필요 없다. 

또 오름차순이어야하므로 만약 3을 뽑았다면 3보다 큰 숫자들이 뒤에 나와야한다. 그렇기 때문에 시작하는 인덱스를 늘리며 계산해주어야한다.

N을 입력받으면 1 ~ N 까지의 수로 순열을 만들면 되기 때문에 별다른 배열 없이 인덱스로만 구성하면 된다. 

#include <iostream>
#include <vector>
using namespace std;
int n, m;

vector<int>temp;
int visited[9] = { false };

void backtracking(int cnt, int idx) {
	if (cnt == m) {
		for (int i = 0; i < temp.size(); i++) printf("%d ", temp[i]);
		printf("\n");
		return;
	}
	for (int i = idx; i <= n; i++) {
		temp.push_back(i);
		backtracking(cnt + 1 , i);
		temp.pop_back();
	
	}
}

int main() {
	scanf("%d %d", &n, &m);
	backtracking(0 , 1);
}

www.acmicpc.net/problem/15652

15652번: N과 M (4)