굳건하게

문제 : https://www.acmicpc.net/problem/17471

[ 알고리즘풀이 ]

1. N이 최대 10이므로 1 ~ N을 A, B 두 그룹으로 나눌 수 있는 모든 경우에 대해서 백트레킹으로 모든 경우의 수를 구하고, 각 경우마다 투표를 진행합니다.

2. 투표를 진행할 때, 현재 A, B로 나누어진 선거구가 투표가 가능한지 체크를 해줍니다.

먼저, A, B 두 그룹 중 하나라도 비어있으면 안 됩니다. 또, A, B 두 그룹이 각각 연결되어있어야 합니다.

따라서 어떤 그룹이 비어있는지 아닌지 체크를 먼저 하고, 그 그룹에 해당되는 지역들을 제외하고 나머지 지역은 visited 에 check를 한 후 BFS 탐색을 진행해 그룹에 속해있는 지역들끼리 서로 연결되어있는지 확인합니다.

3. (2) 에서 투표가 가능하다면, 각 선거구 별로 인구수를 계산해 답을 갱신합니다.

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

int N, M, K, ans = 987654321;
int population[11] = {};
bool map[11][11] = {};
vector<int> A, B;

bool checkPossible(vector<int> K) {
	if (K.empty())
		return false;
	bool visited[11] = {};
	for (int i = 1; i <= N; i++)
		visited[i] = true;
	for (int i = 0; i < K.size(); i++)
		visited[K[i]] = false;
	// BFS탐색
	queue<int> q;
	q.push(K[0]);
	visited[K[0]] = true;
	while (!q.empty()) {
		int s = q.front();
		q.pop();
		for(int i = 1; i <= N; i++)
			if (map[s][i] == 1 && visited[i] == false) {
				visited[i] = true;
				q.push(i);
			}
	}
	for (int i = 1; i <= N; i++)
		if (visited[i] == false)
			return false;
	return true;
}

void playVote() {
	int sumA = 0, sumB = 0;
	if (checkPossible(A) && checkPossible(B)) {
		for (int i = 0; i < A.size(); i++)
			sumA += population[A[i]];
		for (int i = 0; i < B.size(); i++)
			sumB += population[B[i]];
		ans = min(ans, abs(sumA - sumB));
	}
	return;
}
void func(int c) {
	if (c == N) {
		playVote();
		return;
	}
	A.push_back(c + 1);
	func(c + 1);
	A.pop_back();
	B.push_back(c + 1);
	func(c + 1);
	B.pop_back();
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> population[i];
	for (int i = 1; i <= N; i++) {
		cin >> M;
		for (int j = 0; j < M; j++){
			cin >> K;
			map[i][K] = true;
			map[K][i] = true;
		}
	}
	func(0);
	if (ans == 987654321)
		cout << "-1\n";
	else
		cout << ans;
	return 0;
}

문제 : https://www.acmicpc.net/problem/2565

[ 알고리즘풀이 ]

 전깃줄의 상태가 들어오면 한쪽을 기준으로 sorting 한 후, 다른 쪽에서 LIS를 구하면 정답을 얻어낼 수 있습니다.

예시)

 왼쪽 전봇대를 기준으로 Sorting을 해보겠습니다.

 그 후, 왼쪽 전봇대는 Sorting이 되었으므로, 오른쪽 전봇대에서 가장 긴 증가하는 부분 수열을 찾는다면 그 부분 수열은 왼쪽 전봇대는 이미 Sorting 되어 있고, 오른쪽 전봇대에서도 증가하고 있으므로 서로 엉키지 않습니다! 즉, 서로 최대한 교차하지 않는 상태가 됩니다. 따라서, 가장 긴 증가 부분 수열의 길이를 구하고 N에서 빼준다면 제거해야 되는 전깃줄의 최소 개수를 얻어낼 수 있습니다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

	int N, a, b, dp[100] = {};
	vector<pair<int, int>> v;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		v.push_back(make_pair(a, b));
	}
	sort(v.begin(), v.end());
	// LIS구하는부분
	dp[0] = 1;
	for (int i = 1; i < N; i++) {
		int m = 0;
		for (int j = 0; j < i; j++)
			if (v[j].second < v[i].second)
				m = max(m, dp[j]);
		dp[i] = m + 1;
	}
	int m = 0;
	for (int i = 0; i < N; i++)
		m = max(dp[i], m);
	cout << N - m;
}

문제 : https://www.acmicpc.net/problem/1059

[ 알고리즘풀이 ]

Lucky Set을 정렬한 후, N의 상대적인 위치를 파악해 Lucky Set에서 left, right 를 설정합니다.

left 와 N이 같다면 0을 출력하고 아니라면 경우의 수를 모두 출력해주면 됩니다.

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int N, list[1002] = {}, L, left, right;
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> list[i];
	sort(list, list + N + 1);

	cin >> L;
	for (int i = 0; i <= N; i++)
		if (list[i] <= L && L < list[i + 1]) {
			left = list[i];
			right = list[i + 1];
			break;
		}
	if (L == left)
		cout << 0;
	else
		cout << (L - left) * (right - L) - 1;
	return 0;
}

문제 : https://www.acmicpc.net/problem/17281

[ 알고리즘풀이 ]

1. Backtracking 을 이용해 가능한 모든 타순에 대해서 게임을 진행합니다. ( 이때, 1번 선수는 4번 타자로 선발된 경우만 게임을 진행합니다. )

2. 게임은 N 이닝 동안 현재 주자 상태와 현재 타석에 있는 타자의 결과에 따라서 score를 계산해주면 됩니다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N, result[50][9] = {}, ans = -1;

int startGame(vector<int> batting) {
	int score = 0, batter = 0, out = 0;
	for (int i = 0; i < N; i++) {
		out = 0;
		bool runner[3] = {};
		while (out < 3) {
			if (result[i][batting[batter]] == 0)
				out++;
			else {
				// 기존에 있던 주자들
				for (int j = 2; j >= 0; j--) {
					if(runner[j]){
						if (j + result[i][batting[batter]] >= 3)
							score++;
						else
							runner[j + result[i][batting[batter]]] = true;
						runner[j] = false;
					}
				}
				// 타자
				if (result[i][batting[batter]] == 4)
					score++;
				else
					runner[result[i][batting[batter]] - 1] = true;
			}

			batter = (batter + 1) % 9;
		}
	}
	return score;
}

void backTracking(vector<int> batting, bool check[9]) {
	if (batting.size() == 9) {
		if(batting[3] == 0)
			ans = max(ans, startGame(batting));
		return;
	}
	for(int i = 0; i < 9; i++)
		if (!check[i]) {
			batting.push_back(i);
			check[i] = true;
			backTracking(batting, check);
			check[i] = false;
			batting.pop_back();
		}
	return;
}

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

	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < 9; j++)
			cin >> result[i][j];

	vector<int> batting;
	bool check[9] = {};
	for (int i = 0; i < 9; i++) {
		batting.push_back(i);
		check[i] = true;
		backTracking(batting, check);
		check[i] = false;
		batting.pop_back();
	}
	cout << ans;
	return 0;
}