기록을

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

연구소 3을 해결했다면 거저 먹을 수 있는 문제이다.

기본적으로 바이러스의 후보지들을 가지고 조합을 구해야 한다.

바이러스 후보지가 5곳이고 m = 3으로 주어진다면, 5Cm만큼의 경우의 수를 확인해보면 답을 찾을 수 있다.

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

C개의 수를 입력받아서 길이 L의 수열을 출력하면 된다.

입력은 소문자로만 들어오고, 정렬되어서 들어오지 않는다.

출력되는 수열은 오름차순 정렬 상태여야 하기 때문에 입력을 받은 이후에 정렬이 필요하다. 그리고 사전순의 상태를 유지하기 위해서 st라는 변수를 두어서 이전에 사용된 문자의 인덱스를 관리한다.

문자의 길이가 0이 되면 이 전에 사용한 문자의 인덱스가 존재하지 않기 때문에 0으로 처리해준다.

문자를 중복해서 사용할 수 없기 때문에 특정 인덱스의 문자가 사용중인지 여부를 판단하는 배열이 필요하다.

출력되는 문자열의 문자 사이사이에 공백이 당연히 포함된다고 생각해서 공백까지 출력해서 맞왜틀을 반복했다.

출력 형식을 잘 확인하도록 하자.

#include<iostream>
#include<algorithm>
using namespace std;
int L, C, st;
char n[15], arr[15];
bool isused[15];
bool Check() {
	int cntM = 0, cntJ = 0;
	for (int i = 0; i < L; i++) {
		if (arr[i] == 'a' or arr[i] == 'e' or
			arr[i] == 'i' or arr[i] == 'o' or arr[i] == 'u')
			cntM++;
		else
			cntJ++;
	}
	if (cntM >= 1 && cntJ >= 2) //모음1, 자음2개가 있어야 true
		return true;
	else
		return false;
}
void func(int k) {
	if (k == L) {
		if (Check()) {
			for (int i = 0; i < L; i++)
				cout << arr[i];
			cout << '\n';
		}
		return;
	}
	if (k == 0) st = 0;
	for (int i = st; i < C; i++) {
		if (!isused[i]) {
			arr[k] = n[i];
			isused[i] = true;
			st = i;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	cin >> L >> C;
	for (int i = 0; i < C; i++)
		cin >> n[i];
	sort(n, n + C);
	
	func(0);
	return 0;
}

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

사용했던 숫자를 여러 번 사용할 수 있다.

따라서 숫자 사용 여부를 관리하는 배열이 필요하지 않다.

수열을 벡터에 쌓고, 원하는 길이만큼 쌓이면 set에 넣고 벡터를 비워주는 것을 반복한다.

set에는 중복되는 원소가 들어갈 수 없다는 것을 활용했다.

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int m, n, num[8], arr[8], Start;
set<vector<int> > st;
void func(int k) {
	if (k == m) {
		vector<int> v;
		for (int i = 0; i < m; i++)
			v.push_back(arr[i]);
		st.insert(v);
		v.clear();
		return;
	}
	if (k == 0) Start = 0;
	for (int i = Start; i < n; i++) {
		arr[k] = num[i];
		Start = i;
		func(k + 1);
	}

}
int main(void) {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	sort(num, num + n);
	func(0);
	set<vector<int> >::iterator itr;
	for (itr = st.begin(); itr != st.end(); itr++) {
		vector<int> tmp = *itr;
		for (int i = 0; i < tmp.size(); i++)
			cout << tmp[i] << ' ';
		cout << '\n';
	}
	return 0;
}

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

숫자의 입력이 중복되어서 들어올 수 있다.

결과로 나오는 수열은 오름차순으로 정렬되는 상태여야 한다. 하지만 입력은 정렬되어서 들어오는 것이 아니기 때문에 입력을 모두 받은 이후에 오름차순 정렬을 해줘야 한다.

또한, 사용했던 숫자를 재사용할 수 있기 때문에 숫자의 사용 중 여부를 판단하는 배열 또한 필요하지 않다.

그리고 수열이 중복되어서 생성될 수 있는데, 이는 중복을 허용하지 않는 set을 활용해서 처리했다.

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int m, n, arr[7], num[7];
set<vector<int > > st;
vector<int> v;
void func(int k) {
	if (k == m) {
		for (int i = 0; i < m; i++) {
			v.push_back(arr[i]);
		}
		st.insert(v);
		v.clear();
		return;
	}
	for (int i = 0; i < n; i++) {
		arr[k] = num[i];
		func(k + 1);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	sort(num, num + 1);
	func(0); //0번까지 채워져있다
	set<vector<int> >::iterator itr;
	for (itr = st.begin(); itr != st.end(); itr++) {
		vector<int> tmp = *itr;
		for (int i = 0; i < tmp.size(); i++)
			cout << tmp[i] << ' ';
		cout << '\n';
	}
	return 0;
}

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

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

조합과 관련된 문제라고 기억한다. 조합과 백트레킹을 매끄럽게 다룰 수 있었다면 조금 더 빠르게 풀고 넘어갈 수 있었던 문제였다. 역량테스트 A형스러운 문제였던 기억이 난다.

가장 기본적으로 소수를 판별할 수 있어야 한다.

다음으로 정수의 자리수를 없애는 방식으로 수의 변화가 일어난다. 따라서 문자열 처리를 해주면 되겠다.

정수의 자리수에서 하나의 숫자를 지우는 것을 조합의 개념으로 이해하고, 문제를 풀이했다.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
bool isPrime(int n) {
	if (n == 1) return false;
	for (int i = 2; i * i <= n; i++)
		if (n % i == 0) return false;
	return true;
}
int Max = -1;
int func(int n, int res) {
	
	string str = to_string(n);
	
	if (str.length() == 1) {
		if (isPrime(n)) {
			res++;
			if (Max < res) Max = res;
			//printf("\n %d 일 때 res는 %d\n", n, res);
			return res;
		}
		else {
			if (Max < res) Max = res;
			return res;
		}
	}
	
	if (isPrime(n)) {
		res++;
		if (Max < res) Max = res;
		//printf("\n %d 일 때 res는 %d\n", n, res);
	}
	else {
		//cout << n << "은 소수가 아님\n";
		if (Max < res) Max = res;
		return res;
	}
	
	//vector<int> a; //몇개의 수에서
	int a[6];
	
	for (int i = 0; i < str.length(); i++) {
		a[i] = stoi(str.substr(i, 1));
	}
	
	int select[7] = { 0,1,1,1,1,1,1 };
	
	do {
		string temp;
		for (int i = 0; i < str.length(); i++) {
		
			if (select[i])
				temp = temp + to_string(a[i]);
		}
		//cout << temp << ' ' << res << '\n';
		func(stoi(temp.substr(0,temp.length())),res);
	}while (next_permutation(select, select + str.length()));

}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tc;
	cin >> tc;
	for (int T = 1; T <= tc; T++) {
		cout << "Case #" << T << '\n';
		Max = -1;
		int a, b;
		cin >> a >> b;
		func(a, 0);
		int MaxA = Max;
		Max = -1;
		func(b, 0);
		int MaxB = Max;

		//printf("Amax = %d Bmax = %d\n", MaxA, MaxB);
		if (MaxA > MaxB)
			cout << 1 << '\n';
		else if (MaxA < MaxB)
			cout << 2 << '\n';
		else
			cout << 3 << '\n';
	}
	return 0;
}