대엉코딩

오늘은 완전탐색 문제를 풀다가 사용한 c++의 next_permutation 입니다.

사실 알고리즘 동아리를 할 때, 한번 설명을 들은 적이 있어 알고는 있었는데 대부분의 문제풀이 때 그냥 DFS 완탐 으로 모든 경우의 수를 구해서 문제를 풀어왔었는데요.

오랫만에 문제를 풀어서 그럴수도 있겠지만, 익숙치 않은 IDE 에서 짜다보니 코드가 길어질수록 미세한 실수도 많이 나오고 다른 디버깅 환경에서 그 실수를 찾아내기가 생각보다 오래걸려서 next_permutation도 제대로 알아보고 익숙해져볼 생각입니다.

1. 조건

- next_permutation은 정렬을 조건으로 합니다.

- 물론, 원하는 출력에 따라 조건을 변경해서 출력하면 됩니다.

- 기본적인 5개의 후보로 부터 모든 가능한 5개 사이즈의 조합을 구하는 경우,

   이 후보들은 모두 오름차순 정렬이 되어 있어야 합니다. ( ex - 1 2 3 4 5 )

1-1. 

 - 특수한 상황이지만 기존 배열(벡터)의 상태가 { 7, 5, 1, 2, 3 }일 경우,

   7과 5는 앞에 고정된 상태로 1,2,3 만 변경됩니다.

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	vector<int> arr_1{ 1,5,5,7 };

	do {
		for (int i = 0; i < arr_1.size(); i++) {
			cout << arr_1[i] << " ";
		}
		cout << "\n";
	} while (next_permutation(arr_1.begin(), arr_1.end()));
	cout << "\n";

	return 0;
}

** 잘못된 내용이 있으면 알려주세요 **

www.acmicpc.net/problem/18511

1. 풀이방법

- 처음 문제를 보고 눈에 띈 숫자는 N이 최대 100,000,000 이므로 선형적으로 증가시켜가며 N과 비교하면 시간초과

- 그러면 주어진 집합을 보고 숫자를 구성해서 N과 비교를 해야 겠다.

- 그래서 자릿수 계산하고 앞자리 수 부터 비교를 해 가면서 어떤 원소를 자릿수에 넣고 해야겠다~~ 라면서 하다보니

- 되게 다양한 경우의 수가 있고 생각보다 너무 복잡하였습니다.....하

- 그래서 문제를 다시 읽어보니..... 매우 쉬워지는 이유가 하나 있었습니다 K의 원소의 개수가 최대 3개 라는 것....!

- 저는 K의 집합 원소가 1~9 이고 집합의 원소의 수 도 역시 최대 10개라고 당연시? 생각해서...

- 이 모두를 조합하는 수는 너무 많다 라고 생각했었는데 아니였습니다...

- 최대 3개 이므로 그냥 모든 조합을 만들어 내서 N가 비교하고 N보다 작거나 같을경우의 수를 모두 벡터에 넣고

- 그 중 최대값을 출력하였습니다.

2. 주의사항

- 문제를 똑바로 파악하고 시작할 것 !!!!

3. 나의코드

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int n, k,tmp;
vector<int> numarr;
vector<int> resultarr; //n을 쪼개놓자

bool compare(int& lhs, int& rhs) {
	if (lhs > rhs) return true;
	else return false;
}

void makecase(int num,int cnt) {
	if (cnt!=0 && num <= n) { 
		resultarr.emplace_back(num);
	}
	if (num > n) return;
	for (int i = 0; i < k; i++) {
		if (cnt == 0) { makecase(num * numarr[i],cnt+1); }
		else makecase(num*10+numarr[i],cnt+1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> k;
	
	for (int i = 0; i < k; i++) {
		cin >> tmp;
		numarr.emplace_back(tmp);
	}
	sort(numarr.begin(), numarr.end(), compare);
	makecase(1,0);
	sort(resultarr.begin(), resultarr.end(), compare);
	cout << resultarr[0];
	return 0;
}

www.acmicpc.net/problem/17281

- 모든 가능한 순열 case를 모두 구해서 야구 시뮬레이션을 돌려서 가장 큰 점수를 반환해주면 됩니다.

-순열 case만 제대로 모두 구한다면 야구게임 자체를 구현하는 것은 어렵지 않습니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N;
bool playerordercheck[10];
int playerresult[51][10];
int playerorder[10];
bool location[4]; //1루 2루 3루 를 표시
int resultscore;
int maxscore;
void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for(int j=1;j<=9;j++){
			cin >> playerresult[i][j];
		}
	}
}
void resetlocation() { //1,2,3루 초기화
	for (int i = 1; i <= 3; i++) {
		location[i] = false;
	}
	return;
}
void getscorecheck(int num) {
	for (int i = 3; i >= 1; i--) {
		if (location[i] == true) {
			if (i + num >= 4) { location[i] = false; resultscore++; }
			else { location[i] = false; location[i + num] = true; } //주자 이동
		}
	}
	if (num >= 4) { resultscore++; return; } //홈런인 경우
	else { location[num] = true; return; }
}
int gamestart() {
	resultscore = 0;
	int outcount = 0;
	int playerpointer = 1;
	for (int i = 1; i <= N; i++) { //N이닝동안 반복
		outcount = 0; //이닝별 아웃카운터 초기화
		while (1) { //주자 한명씩 확인
			if (outcount == 3) {
				resetlocation(); //나가있던 주자들 모두 들어옴.
				break;
			}
			if (playerresult[i][playerorder[playerpointer]] == 1) { //1루타
				getscorecheck(1);
			}
			else if (playerresult[i][playerorder[playerpointer]] == 2) {//2루타
				getscorecheck(2);
			}
			else if (playerresult[i][playerorder[playerpointer]] == 3) {//3루타
				getscorecheck(3);
			}
			else if (playerresult[i][playerorder[playerpointer]] == 4) {//4루타
				getscorecheck(4);
			}
			else { //아웃된 경우
				outcount++;
			}
			playerpointer++;
			if (playerpointer == 10) { playerpointer = 1; } //9번 주자까지 다 치면 다시 1번 주자
		}
	}
	return resultscore;
}
void P(int cnt) {
	if (cnt == 10) {
		int tmp = gamestart();
		if (maxscore < tmp) { //각 case가 확정되면 게임을 시작한다.
			maxscore = tmp;
		} 
		return;
	}
	for (int i = 1; i <= 9; i++) {
		if (playerordercheck[i] == true) continue;//아직 배정되지 않은 선수라면playerordercheck[i] = true;
		playerordercheck[i] = true;
		playerorder[i] = cnt;
		P(cnt + 1); //모든 순열case을 찾자
		playerordercheck[i] = false;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	input();
	playerordercheck[4] = true; //4번타자는 1번으로 고정(문제조건) -이미 자리가 배정됨
	playerorder[4] = 1;
	P(2); //1명은 이미 자리 배정이 완료되었음으로... permutation(순열)
	      //순서를 고려해야함
	cout << maxscore << "\n";

	return 0;
}

- 이번에 짜 본것은 임의의 개수의 카드 수 n 그리고 그 카드의 숫자를 입력 받았을 때

- 그 카드들을 가지고 만들 수 있는 모든경우의 수 를 출력하는 코드 입니다.

- 재귀를 사용하였고

- 알기 쉽게 표현 하자면 예를 들어 10 장의 카드의 모든 경우의 수를 구해야 할 때

- 한장을 선택을 한다면 !  나머지 9장만 선택을 하면됩니다 

- 이러한 방향으로 뽑아야 하는 카드의 수를 하나씩 줄이는 방식으로 구현하였고

- 코드 구현상에서는 임의의 카드를 하나 선택했다고 한다면 그 임의의카드와 벡터의 마지막 index 위치의 수 와 swap

- 을 한 이후 사이즈를 하나줄인 함수로 다시 들어갑니다 (즉 하나의 카드는 선택해서 뺴놓는 느낌)

<코드>