굳건하게

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

[ 알고리즘풀이 ]

( 기존풀이 : https://travelbeeee.tistory.com/288 )

DP[ i ][ j ] : (1, 1) ~ (i , j) 까지 구간의 합. 이라고 정의하면 다음과 같은 점화식이 성립합니다.

DP[i][j] = DP[i - 1][j] + DP[i][j - 1] - DP[i - 1][j - 1] + map[i][j]

#include<iostream>

using namespace std;
int N, M, a, b, c, d, map[1025][1025] = {}, DP[1025][1025] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			DP[i][j] = DP[i - 1][j] + DP[i][j - 1] + map[i][j] - DP[i - 1][j - 1];

	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c >> d;
		cout << DP[c][d] - DP[c][b - 1] - DP[a - 1][d] + DP[a - 1][b - 1] << '\n';
	}
	return 0;
}

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

[ 알고리즘풀이 ]

1. 입력된 배열에서 각 Row 별로 sum 을 담고 있는 sumRow 배열을 정의합니다.

- sumRow[i][j] : i 행 0 ~ j 열까지의 합.

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			sumRow[i][j] = map[i][j] + sumRow[i][j - 1];

O(N^2) 만에 sumRow 배열을 채울 수 있습니다.

2. input이 들어오면 sumRow 배열을 이용해서 O(N) 만에 답을 찾아낼 수 있습니다.

즉, input M개에 대해서 O(N * M) 만에 답을 찾아낼 수 있습니다.

(x1, y1) ~ (x2, y2)의 합을 구해달라고 했을 때, x1 ~ x2 행 별로

sumRow[ ][ y2 ] - sumRow[ ][ y1 - 1] 을 한다면 y1 ~ y2 열의 합을 쉽게 얻어낼 수 있습니다.

#include<iostream>

using namespace std;
int N, M, a, b, c, d, map[1025][1025] = {}, sumRow[1025][1025] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			sumRow[i][j] = map[i][j] + sumRow[i][j - 1];
	for (int i = 0; i < M; i++) {
		int sum = 0;
		cin >> a >> b >> c >> d;
		for (int j = a; j <= c; j++)
			sum += sumRow[j][d] - sumRow[j][b - 1];
		cout << sum << '\n';
	}
	return 0;
}

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

[ 알고리즘풀이 ]

1. 사람마다 원하는 너트롤의 조각을 입력받으면서, 가장 많이 받을 것 같은 사람을 갱신하고 너트롤에 check를 합니다.

2. 너트롤에 check 된 값들을 순회하며 실제로 가장 많이 받은 사람을 뽑습니다.

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int L, N, a, b, l[1001] = {}, n[1001] = {};
	cin >> L >> N;

	int m = -1, index = 0;
	for (int i = 1; i <= N; i++) {
		cin >> a >> b;
		// 기대가 가장 큰 사람 뽑기.
		if ((b - a + 1) > m) {
			m = (b - a + 1);
			index = i;
		}
		for (int j = a; j <= b; j++)
			if(l[j] == 0)
				l[j] = i;
	}

	// 실제로 가장 많이 받는 사람 뽑기.
	m = -1;
	int ans = 0;
	for (int i = 1; i <= L; i++)
		n[l[i]]++;
	for (int i = 1; i <= N; i++)
		if (n[i] > m) {
			m = n[i];
			ans = i;
		}
	cout << index << '\n' << ans;
	return 0;
}

문제 : 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;
}