기록을

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

n개의 숫자중에 6개를 뽑아서 수열을 만들고, 오름차순 정렬하여 출력해주면 된다.

입력으로 들어오는 숫자는 정렬된다는 조건이 없다는 것을 주의해야 한다.

1. next_permutation 활용 구현

#include<iostream>
#include<algorithm>
using namespace std;
int n, a[50], Sel[50];
int main(void) {
	while (1) {
		cin >> n;
		if (n == 0) return 0;
		
		for (int i = 0; i < n; i++)
			cin >> a[i];
		sort(a, a + n);
		for (int i = 0; i < n; i++) {
			if (i < 6) Sel[i] = 0;
			else Sel[i] = 1;
		}
		
		do {
			for (int j = 0; j < n; j++) {
				if (!Sel[j]) cout << a[j] << ' ';
			}
			cout << '\n';
		} while (next_permutation(Sel, Sel + n));
		cout << '\n';
	}
	return 0;
}

2. 백트래킹 활용 구현

마찬가지로 사용할 수 있는 수들을 입력 받은 이후에, 수열을 오름차순으로 만들어내기 위해서 정렬을 수행한다.

조합이기 때문에 매 재귀마다 0부터 확인하는 것이 아니라 이전 재귀에서 사용했던 숫자의 위치를 파악해서 그 숫자 이후로 사용할 수 있는 숫자를 찾는다.

#include<iostream>
#include<algorithm>
using namespace std;
int n, num[50], arr[7];
bool isused[50];
int st;
void func(int k) {
	//여기서 수열의 길이 k
	if (k == 6) {
		for (int i = 0; i < k; i++) {
			cout << arr[i] << ' ';
		}
		cout << '\n';
		return;
	}
	
	if (k == 0) st = 0; //0일때 초기화
	for (int i = st; i < n; i++) { //조합으로 만들기 위해 st부터. 0부터 뽑으면 순열(순서가 다르면 다른 수열)
		if (!isused[i]) {
			isused[i] = true;
			arr[k] = num[i];
			st = i;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	while (1) {
		cin >> n;
		if (n == 0) break;
		for (int i = 0; i < n; i++) {
			cin >> num[i];
		}
		sort(num, num + n);
		func(0);
		cout << '\n';
	}
}

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

정수들의 개수와 목표로 하는 합을 입력받는다.

정수들로 만들 수 있는 길이가 1 이상인 부분 수열들을 구한다. 그리고 그 부분수열들의 합이 처음에 입력받은 S와 같은 부분수열의 개수를 구하면 되는 문제이다.

우선 N개의 숫자를 입력받았다고 가정하면, 1개, 2개, 3개 ... N개로 만들 수 있는 부분수열을 모두 구해야 한다.

그리고 매 부분수열마다 합을 계산해서 그 합이 s인지 아닌지 판단해주면 되는 문제이다.

즉 조합으로 바꿔서 생각할 수 있고, n이 20 이하로 작으니 백트래킹을 해도 무방하다.

직접 재귀로 구현할 수도 있지만 next_permutation을 이용해서 구현했다.

Sel 배열을 우선 만들어 둔다. 가령 6개 중에 4개를 조합으로 뽑는다면,

Sel 배열은 0, 0, 0, 0, 1 1 이렇게 두고 if(!Sel[i]) 일 때 수열이 만들어지게 된다.

이를 이용해서 1개부터 n개까지 부분수열을 구해주면 되겠다.

#include<iostream>
#include<algorithm>
using namespace std;
int n, s, a[20], Sum = 0, Sel[20], cnt = 0;
int main(void) {
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < 20; i++)
		Sel[i] = 1;
	for (int i = 0; i < n; i++) {
		Sel[i] = 0; //하나씩 0으로 바꿈
		do {
			Sum = 0;
			for (int j = 0; j < n; j++) {
				if (!Sel[j]) Sum += a[j];
				//if (!Sel[j]) cout << a[j] << ' ';
			}
			if (Sum == s) cnt++;
		} while (next_permutation(Sel, Sel + n));
	}
	cout << cnt << '\n';
	return 0;
}

next permutation 기본형은 아래와 같다. 배열(벡터)의 다음 사전순 순서를 반환해준다.

1, 2, 3 ,4를 이용해서 만들 수 있는 모든 길이 4짜리 수열을 만드는 코드는 아래와 같다. (순서가 다르면 다른 수열)

#include<iostream>
#include<algorithm>
using namespace std;
int main(void) {
	int a[4] = { 1,2,3,4 };
	do {
		for (int i = 0; i < 4; i++)
			cout << a[i] << ' ';
		cout << '\n';
	} while (next_permutation(a, a + 4));
	return 0;
}

실행 결과는 위와 같다.

다음으로 6개의 숫자 중에서 2개의 숫자를 조합으로 뽑는 경우는 다음과 같다.

#include<iostream>
#include<algorithm>

using namespace std;
int main(void) {
	int a[6] = { 1,5,3,6,2,7 };
	//sort(a, a + 6);
	int Select[6] = { 0,0,1,1,1,1 }; //이러면 조합
	int cnt = 0;
	do {
		cnt++;
		for (int i = 0; i < 6; i++) 
			if (!Select[i]) cout << a[i] << ' ';
		cout << '\n';
	} while (next_permutation(Select, Select + 6));
	//cout << cnt;
	return 0;
}

Select 배열을 가지고 next_permutation을 돌려준다. 뽑고 싶은 숫자의 개수를 0의 개수로 하고 앞에서부터 0을 써주면 된다. 위의 예시는 정렬을 하지 않았는데, 사용할 수 있는 숫자를 그대로 두고 실행했을 때 어떤 결과가 나오는지 보기 위함이다.

sorting하는 부분의 주석을 풀면, 사전순으로 수열이 정렬되서 나올 것이다.

이제 순열을 구현해보면 다음과 같다. 먼저 배열이 하나 더 필요하다. Select의 값이 0보다 클 때 if문에 진입하게 되고,

Select 값으로 index를 맞춰야 하는데 1부터 시작하므로 1씩 빼서 seq에 담아준 것이다. 

#include<iostream>
#include<algorithm>

using namespace std;
int main(void) {
	int a[6] = { 1,5,3,6,2,7 };
	//sort(a, a + 6);
	int Select[6] = { 0,0,0,0,1,2 }; 
	int cnt = 0;
	do {
		//cnt++;
		int seq[2] = {};
		for (int i = 0; i < 6; i++)
			if (Select[i]) seq[Select[i] - 1] = a[i];
		for (int i = 0; i < 2; i++) cout << seq[i] << ' ';
		cout << '\n';
	} while (next_permutation(Select, Select + 6));
	//cout << cnt;
	return 0;
}