pushback

두 팀으로 나누기만 하면 되는 문제다.

스타트 팀이 될 사람만 체크하고, 스타트 팀과 링크 팀이 완성되면 두 팀의 전력차를 계산하자.

여기서, 한가지 재미있는 점은 4명이 있다고 가정했을 때,

1. 스타트 팀 : (0 ,1), 링크 팀 : (2, 3)
2. 스타트 팀 : (2, 3), 링크 팀 : (0, 1)

이 두 가지 경우는 사실상 같은 경우이다.

왜냐하면, (0, 1)이 스타트 팀인지 링크 팀인지 상관없다. 그냥 (0, 1)이 같은 팀이기만 하면 되기 때문이다.

이 사실을 이용하면 시간 복잡도를 줄일 수 있다.

1. naive하게 구현

#include <bits/stdc++.h>
using namespace std;

const int INF = 2147483647;

int n;
bool isStartTeam[21]; // 어떤 사람이 스타트 팀이지 체크
int sTeam[21], lTeam[21]; // 각 팀의 팀원 목록
int power[21][21]; // 능력치 저장
int ans = INF; // 답

// cur은 몇번부터 뽑을 차례인지, cnt은 몇명을 뽑았는지
void recur(int cur, int cnt) {

	if (cnt == n / 2) {
		int curStart = 0, curLine = 0;
		// 스타트팀과 링크팀을 나눔.
		for (int i = 0; i < n; ++i) {
			if (isStartTeam[i]) sTeam[curStart++] = i;
			else lTeam[curLine++] = i;
		}
		// 전력 계산
		int sPower = 0, lPower = 0;
		for (int i = 0; i < n / 2; ++i) for (int j = 0; j < n / 2; ++j) {
			sPower += power[sTeam[i]][sTeam[j]];
			lPower += power[lTeam[i]][lTeam[j]];
		}
		
		// 답 갱신
		ans = min(ans, abs(sPower - lPower));
		
		return;
	}

	for (int i = cur; i < n; ++i) {
		isStartTeam[i] = true;
		
		recur(i + 1, cnt + 1);

		isStartTeam[i] = false;
	}
}


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

	cin >> n;
	for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> power[i][j];

	recur(0, 0);

	cout << ans;
	return 0;
}

2. 같은 경우를 제거

#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;

int n;
bool isStartTeam[21];
int sTeam[21], lTeam[21];
int power[21][21];
int ans = INF;

void recur(int cur, int cnt) {

	if (cnt == n / 2) {
		int curStart = 0, curLine = 0;

		for (int i = 0; i < n; ++i) {
			if (isStartTeam[i]) sTeam[curStart++] = i;
			else lTeam[curLine++] = i;
		}

		int sPower = 0, lPower = 0;
		for (int i = 0; i < n / 2; ++i) for (int j = 0; j < n / 2; ++j) {
			sPower += power[sTeam[i]][sTeam[j]];
			lPower += power[lTeam[i]][lTeam[j]];
		}

		ans = min(ans, abs(sPower - lPower));

		return;
	}
	
	// for문의 범위가 바뀜
	for (int i = cur; i < n / 2 + cnt; ++i) {
		isStartTeam[i] = true;

		recur(i + 1, cnt + 1);

		isStartTeam[i] = false;
	}
}


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

	cin >> n;
	for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> power[i][j];

	recur(0, 0);

	cout << ans;
	return 0;
}

확실히 빨라졌다.

브루트포스 문제이다.

백트래킹을 사용하여 모든 경우를 탐색해주자. 

연산자 개수가 10개 밖에 안돼서 next_permutation으로 해결하는 방법도 있다.

1. 백트래킹

#include <bits/stdc++.h>
using namespace std;

int n;
int num[12];
int cal[4];
int maxANS = -1'000'000'001; // 답의 범위는 -10억 ~ 10억
int minANS = 1'000'000'001;

void recur(int sum, int cur) {
	// 한번의 탐색이 끝나면, 최댓값 최솟값 갱신
	if (cur == n) {
		maxANS = max(maxANS, sum);
		minANS = min(minANS, sum);
		return;
	}

	for (int i = 0; i < 4; ++i) {
		// i번 연산자가 남아있지 않은 경우 다음 연산자로 넘어감
		if (cal[i] == 0) continue;
        
		// i번 연산자를 1개 사용
		--cal[i];
		if (i == 0) recur(sum + num[cur], cur + 1);
		else if (i == 1) recur(sum - num[cur], cur + 1);
		else if (i == 2) recur(sum * num[cur], cur + 1);
		else if (i == 3) recur(sum / num[cur], cur + 1);
        
		// 사용이 끝났으니 사용한 연산자 반납
		++cal[i];
	}
}

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

	cin >> n;
	for (int i = 0; i < n; ++i) cin >> num[i];
	for (int i = 0; i < 4; ++i) cin >> cal[i];
	
	recur(num[0], 1);
	cout << maxANS << '\n' << minANS;
	return 0;
}

2. next_permutation()

#include <bits/stdc++.h>
using namespace std;

int num[11];
int maxANS = -1'000'000'001;
int minANS = 1'000'000'001;
vector<int> calc;

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

	int n, numOfCases;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> num[i];
        
	// 연산자 나열
	for (int i = 0; i < 4; i++)
	{
		cin >> numOfCases;
		while (numOfCases--) calc.push_back(i);
	}

	// 나올 수 있는 경우의 수 계산 == 팩토리얼 연산
	numOfCases = 1;
	for (int i = 1; i <= n - 1; i++) numOfCases *= i; 
	
	while(numOfCases--) {
		int tmp = num[0];
		for (int j = 1; j < n; j++)
		{
			switch (calc[j - 1])
			{
			case 0:
				tmp += num[j];
				break;
			case 1:
				tmp -= num[j];
				break;
			case 2:
				tmp *= num[j];
				break;
			case 3:
				tmp /= num[j];
				break;
			}
		}
		minANS = min(minANS, tmp);
		maxANS = max(maxANS, tmp);
		next_permutation(calc.begin(), calc.end()); // 다음 경우
	}

	cout << maxANS << '\n' << minANS;

	return 0;
}

가능하다고 했지 빠르다곤 안했다.. ㅎㅎ

백트래킹은 중간 연산 결과를 이용할 수 있어서 속도가 빠르지만,

이 풀이는 매 경우마다 계산을 다 해주어야해서 당연히 속도가 느리다.

백트래킹으로 빈칸마다 들어갈 수 있는 수를 찾아 넣어주자.

그러다보면 빈칸임에도 불구하고 넣을 수 있는 숫자가 없는 경우가 있다.

이 경우엔 앞에서 잘못된 숫자가 들어간 것이기 때문에, 다시 뒤로 돌아가자.

\((x, y)\)번째 칸에 넣을 수를 찾는 방법은 1부터 9까지 돌면서

1. \(x\)번째 행에 어떤 수 \(n\)이 존재하는지
2. \(y\)번째 열에 어떤 수 \(n\)이 존재하는지
3. \(((x / 3), (y / 3))\)번 정사각형 안에 어떤 수 n이 존재하는지 (하단 그림 참조)

   

확인해주면 된다.

1. bool 배열로 구현

#include <bits/stdc++.h>
using namespace std;

int sudoku[9][9];
bool row[9][10]; // 행
bool col[9][10]; // 열
bool block[3][3][10]; // 3x3 정사각형
vector<pair<int, int>> blank; // 빈칸들의 좌표

void recur(int cur) {
	// 모든 칸이 채워졌다면 출력 후, exit(0)을 통해 바로 프로그램 종료
	if (blank.size() == cur) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) cout << sudoku[i][j] << ' ';
			cout << '\n';
		}
		exit(0);
	}
    
	int x = blank[cur].first;
	int y = blank[cur].second;

	for (int i = 1; i < 10; ++i) {
		// i라는 숫자가 현재 칸이 속한 행, 열, 3x3 정사각형 안에 존재하는 지 확인
		// 한 곳이라도 존재하면 다음 숫자로 넘어감
		if (row[x][i] || col[y][i] || block[x / 3][y / 3][i]) continue;

		// (x, y)에 i라는 숫자를 채워넣음
		row[x][i] = true;
		col[y][i] = true;
		block[x / 3][y / 3][i] = true;
		sudoku[x][y] = i;
        
		recur(cur + 1); // 다음 칸으로 넘어가기
		
		// 호출한 재귀함수가 리턴됐다는 것은, 현재 빈칸에 i라는 숫자가 들어가면 안된다는 의미
		// 다른 숫자를 채워넣기 위해, (x, y)에서 i라는 숫자를 제거
		row[x][i] = false;
		col[y][i] = false;
		block[x / 3][y / 3][i] = false;
		sudoku[x][y] = 0;
	}
}

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

	for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) {
		cin >> sudoku[i][j];
		// 입력받은 수를 행, 열, 3x3 정사각형에 추가
		row[i][sudoku[i][j]] = true;
		col[j][sudoku[i][j]] = true;
		block[i / 3][j / 3][sudoku[i][j]] = true;

		if (sudoku[i][j] == 0) blank.push_back({ i, j });
	}

	recur(0);

	return 0;
}

2. 비트 연산으로 구현

#include <bits/stdc++.h>
using namespace std;

int sudoku[9][9];
int row[9];
int col[9];
int block[3][3];
vector<pair<int, int>> blank;

void recur(int cur) {

	if (blank.size() == cur) {
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) cout << sudoku[i][j] << ' ';
			cout << '\n';
		}
		exit(0);
	}
    
	int x = blank[cur].first;
	int y = blank[cur].second;

	for (int i = 1; i < 10; ++i) {
		int bit = (1 << i);

		if ((row[x] & bit) || (col[y] & bit) || (block[x / 3][y / 3] & bit)) continue;

		row[x] |= bit;
		col[y] |= bit;
		block[x / 3][y / 3] |= bit;
		sudoku[x][y] = i;
		recur(cur + 1);
		
		row[x] &= (~bit);
		col[y] &= (~bit);
		block[x / 3][y / 3] &= (~bit);
		sudoku[x][y] = 0;
	}
}

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

	for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) {
		cin >> sudoku[i][j];
		row[i] |= (1 << sudoku[i][j]);
		col[j] |= (1 << sudoku[i][j]);
		block[i / 3][j / 3] |= (1 << sudoku[i][j]);

		if (sudoku[i][j] == 0) blank.push_back({ i, j });
	}

	recur(0);

	return 0;
}

bit연산으로 구현하면 빨라질까 해서 구현해봤지만.. 아무래도 메모리접근 한번보다는 비트연산의 비용이 더 비싼 것 같다.

너무나도 유명한 문제이다.

세상에 수많은 풀이 방법이 공개되어있으니 한번 검색해보는 것을 추천한다.

이 문제는 널널한 시간을 줬음에도 불구하고, 아무생각 없이 모든 경우를 탐색하면 시간초과이다.

여기서 내가 말하는 모든 경우 탐색이란, Queen을 같은 칸이 아닌 곳에 일단 박아놓고 Queen끼리 서로 공격할 수 있는지 확인하는 무지성 방법이다.

대충 시간복잡도 계산해보면,

• 퀸을 놓는 경우 = \(O( _{225}P_{15})\)
• 서로 공격할 수 있는지 확인하는 데 걸리는 시간 = \(O(15^2)\)

매 경우마다 공격할 수 있는지 확인해야하니 둘을 곱하면.... 대충 생각해봐도 어질어질한 수치이다.

그래서 이 문제는 처음부터 서로 공격하지 못하게 놓는게 포인트이다.

그렇게 하기 위해 Queen은 8방향 모두 움직일 수 있다는 특성을 이용하자.

Queen이 8방향을 다 갈 수있다 == 어떤 Queen 하나를 놓았을 때, 이 Queen이 속하는 행, 열, 대각선 2개 위에 더 이상 다른 Queen이 올라오면 안된다는 것이다.

그럼 어떻게 코딩할 것인가 ?

재귀함수는 x번 행에서 y번 열에 Queen을 놓을 수 있는지 확인한다. y번 열에 놓을 수 있는지 판단하기 위해서, (x, y)의 값을 통해

• x번 행 위에 Queen이 존재하는지
• y번 열 위에 Queen이 존재하는지
• (x, y)를 포함하고 왼쪽 위에서 오른쪽 아래로 떨어지는 대각선 위에 Queen이 존재하는지
• (x, y)를 포함하고 오른쪽 위에서 왼쪽 아래로 떨어지는 대각선 위에 Queen이 존재하는지

를 보면 된다.

만약 놓을 수 있다면, (x, y)가 속한 모든 선을 true로 바꿔주고 다른 행으로 넘어가면 된다.

대각선을 판단하는게 좀 어려울 수도 있는데, 이것만 알아두면 된다.

• 왼쪽 위에서 오른쪽 아래로 떨어지는 "같은" 대각선에 속한 칸들의 (행 - 열) 값은 모두 동일하다.
• 오른쪽 위에서 왼쪽 아래로 떨어지는 "같은" 대각선에 속한 칸들의 (행 + 열) 값은 모두 동일하다.

코드를 보자.

#include <bits/stdc++.h>
using namespace std;

bool row[16]; // 행
bool col[16]; // 열
bool crossFromRight[31]; // 대각선 오른쪽 위에서 왼쪽 아래
bool crossFromLeft[31]; // 대각선 왼쪽 위에서 오른쪽 아래
int n;

void setFlag(int& line, int& i, bool flag) {
	row[line] = col[i] = crossFromRight[line + i] = crossFromLeft[i - line + 15] = flag;
}

void recur(int line, int& cnt) {
	// n개의 라인에 Queen을 모두 놓은 경우
	if (line == n) {
		cnt++;
		return;
	}

	for (int i = 0; i < n; ++i) {
		if (!row[line] && !col[i] && !crossFromRight[line + i] && !crossFromLeft[i - line + 15]) {
			setFlag(line, i, true);
			recur(line + 1, cnt);
			setFlag(line, i, false);
		}
	}
}


int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int cnt = 0;
	cin >> n;

	recur(0, cnt);

	cout << cnt;

	return 0;
}

내 코드는.. 좀 많이 느린 편이다. 구글링을 통해 더 빠른 코드들을 구경해보는 것도 좋을 것 같다.

0ms 걸리는 코드들은 그냥 https://oeis.org/A000170 이걸보고 바로 답을 출력한 것 같다.

비내림차순.. 별 거 없다. 

이전 재귀함수에서 뽑힌 숫자부터 for문을 돌려주면 된다.

#include <bits/stdc++.h>
using namespace std;

int N, M;
string ans;

void recur(int prev, int cnt) {

	if (cnt == M) {
		ans.back() = '\n';
		cout << ans;
		return;
	}

	for (int cur = prev; cur <= N; ++cur) {
		ans += cur + '0';
		ans += ' ';
		recur(cur, cnt + 1);
		ans.pop_back();
		ans.pop_back();
	}
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> N >> M;

	recur(1, 0);

	return 0;
}

중복을 신경쓰지 않기 때문에, 재귀함수 내 for문은 1부터 N까지 돌자. 재귀함수를 M번 호출하면 끝.

참고로, 답을 int형 배열이 아닌 string에 저장하면 입출력 속도가 월등히 빨라진다.

1. int형 배열에 답 저장

#include <bits/stdc++.h>
using namespace std;

int N, M;
int ans[9];

void recur(int cnt) {

	if (cnt == M) {
		for (int i = 0; i < M; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int cur = 1; cur <= N; ++cur) {
		ans[cnt] = cur;
		recur(cnt + 1);
	}
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> N >> M;

	recur(0);

	return 0;
}

2. string에 답 저장

#include <bits/stdc++.h>
using namespace std;

int N, M;
string ans;

void recur(int cnt) {

	if (cnt == M) {
		ans.back() = '\n';
		cout << ans;
		return;
	}

	for (int cur = 1; cur <= N; ++cur) {
		ans.push_back(cur + '0');
		ans.push_back(' ');
        
		recur(cnt + 1);
        
		ans.pop_back();
		ans.pop_back();
	}
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> N >> M;

	recur(0);

	return 0;
}

재귀 함수를 돌 때, (이전 재귀함수에서 선택된 수 + 1) ~ N까지 for문을 돌리면 된다.

오름차순으로  출력해야되기 때문에 N과 M (1)에서 사용한 isTrue라는 bool형 배열도 필요없다.

왜 ? 선택되는 순서 자체가 오름차순이기 때문.

#include <bits/stdc++.h>
using namespace std;

int N, M;
int ans[9];

void recur(int prev, int cnt) {

	if (cnt == M) {
		for (int i = 0; i < M; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}

	for (int cur = prev + 1; cur <= N; ++cur) {
		ans[cnt] = i;
		recur(cur, cnt + 1);
	}
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> N >> M;

	recur(0, 0);

	return 0;
}

개인적으로 백트래킹이나 브루트포스나 큰 차이가 없다고 생각한다.

그래도 백트래킹이라고 하면, 보통 재귀 함수를 통해 모든 경우의 수를 탐색하는 것을 말한다.

나중에 가지치기(pruning)라는 기법으로 탐색 시간을 줄일 수 있다.

기법이라고 해서 좀 어려워보이는데.. 그냥 조건문을 통해 더 탐색을 할 것인지 결정해주는 거라고 보면 된다.

N과 M 시리즈는 별 거 없다. 백트래킹으로 문제에서 원하는 조건만 잘 지켜주면 해결 가능하다.

코드 재사용을 통해 어떤 조건을 어떻게 바꿔야 하는지 훈련하면 좋을 것 같다.

#include <bits/stdc++.h>
using namespace std;

int N, M;
bool isTrue[9]; // 이미 뽑힌 숫자인지 ?
int ans[9]; // 답 저장

// cnt : 몇 개가 뽑혔는지
void recur(int cnt) {
	// 원하는 개수가 다 뽑혔다면 답 출력
	if (cnt == M) { 
		for (int i = 0; i < M; ++i) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}
    
	// 1 ~ N까지 돌면서 안뽑힌 숫자를 뽑고 다음 재귀함수 호출
	for (int i = 1; i <= N; ++i) {
		if (isTrue[i]) continue;

		isTrue[i] = true;
		ans[cnt] = i;
		recur(cnt + 1);
		// 호출이 끝나면 뽑힌 숫자를 놓아준다.
		isTrue[i] = false;
	}
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> N >> M;

	recur(0);
	
	return 0;
}