기록을

https://swexpertacademy.com/main/code/problem/problemList.do?problemTitle=SW&orderBy=PASS_RATE&select-1=&pageSize=10&pageIndex=1#none

음식 하나에 들어가는 재료는 n/2개이다. 조합을 이용해서 음식 하나에 들어갈 수 있는 재료를 뽑는다.

여기서 뽑힌 재료가 음식 하나에 들어가는 재료가 되는 것이고, 뽑히지 않은 재료는 나머지 음식에  들어가는 재료가 된다.

뽑은 재료들 사이에 시너지를 계산하기 위해서, 순열로 2개를 뽑는다.

나머지 음식에 대해서도 시너지를 계산해준다.

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

배열 돌리기 목록을 꼭 "모두 사용해야 한다"고 했다. 또한 배열을 돌리는 순서에 따라서 결과가 달라지기 때문에, 순열을 사용해서 돌릴 순서를 정해준다.

모든 경우를 다 돌려봐야 하고, 주의할 사항은, 한 순열을 돌린 이후에, 반드시 배열을 원래 상태로 초기화 시켜줘야 한다는 것이다.

배열을 돌릴 때에는, 모든 값을 보존하면서 돌리는 것이 불가능 하다. 돌리는 순서, 방향에 따라서 반드시 모서리중 어느 한 값은 손실이 발생할 수 밖에 없는데, 그 값을 정해서 미리 담아두고, 마지막에 채워주면 된다.

본인은 가장 좌측 상단의 값을 기억해두고, 그 위치를 없어지는 값으로 정했다. 마지막에 그 값이 옮겨가야 할 곳에 넣어주면 된다.

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

순열과 조합을 적절히 사용해주면 되는 문제였다.

먼저 팀을 나누기 위해서는 순서는 중요하지 않기 때문에 조합으로 뽑는다.

0, 1, 2, 3, 4, 5 이렇게 6명의 사람이 있으면 조합으로 3개를 뽑아서 두 개의 팀을 만들어 준다.

이어서 팀 각각에 대해서 보자.

예를 들어 스타트 팀이 0, 1, 2로 결정되면 링크 팀은 자연스럽게 3, 4, 5로 결정된다.

이제 팀 각각에 대해서 점수를 계산해주면 된다.

S01과 S10이 다르다고 했다. 따라서 스타트팀의 경우에 대해서 순열로 뽑아준다. 총 3P2가지가 나올 것이다.

이를 더해서 점수 하나를 만들어주고, 링크팀에 대해서도 진행해준다. 이제 점수차이의 최솟값을 찾으면 된다.

점수 계산시 순열을 사용하지 않고, 조합으로 뽑은 이후에, 순서를 뒤집어서 계산을 추가해줘도 동일한 결과가 나온다. 하지만 순열로 처리하면 한 번에 처리할 수 있기 때문에 순열을 사용했다.

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