취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24452번 문제인 交易計画 (Trade Plan)이다.
문제는 아래 링크를 확인하자.

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

그래프가 주어질 때, 두 노드가 같은 component에 들어있는지 확인하는 작업은 disjoint set 자료구조를 이용해 간단히 할 수 있다. 또한 disjoint set을 rank compression을 기반으로 구현하면 이전 단계에 union한 두 component를 합치기 전으로 빠르게 돌려놓을 수 있게 된다. 이를 이용해 문제를 해결해보자.

구체적인 방법은 다음과 같다. 초기상태로 한 나라의 도시끼리를 잇는 도로들을 미리 전처리해두자. 그리고 나라A의 도시 x와 나라B의 도시 y가 나라 A와 B의 도시만을 거쳐 연결되어있는지 묻는 쿼리들을 몰아 처리해보자. 즉, 나라A와 나라B의 도시를 잇는 에지정보를 이용하여 그래프의 component들을 union하고 쿼리를 처리하자. 쿼리의 처리가 끝났다면 위 과정에서 변형된 그래프를 초기상태(한 나라의 도시끼리 잇는 도로들만 연결된 상태)로 다시 다시 리셋시키자.

쿼리의 순서를 조정하면, 각 에지가 그래프의 component를 합치고 다시 리셋하는 데에 사용되는 횟수는 많아야 1번이 되게 할 수 있다는 점을 관찰하자.

아래는 제출한 소스코드이다.

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

int uf[400001];
int depth[400001];
vector<pair<pair<int, int>, int>> stk;

int findf(int cur) {
	if (cur == uf[cur]) return cur;
	return findf(uf[cur]);
}

void unionf(int x, int y) {
	x = findf(x), y = findf(y);
	if (x == y) return;
	if (depth[x] < depth[y]) {
		uf[x] = y;
		stk.emplace_back(make_pair(make_pair(x, y), 0));
	}
	else if (depth[x] > depth[y]) {
		uf[y] = x;
		stk.emplace_back(make_pair(make_pair(y, x), 0));
	}
	else {
		uf[x] = y;
		depth[y]++;
		stk.emplace_back(make_pair(make_pair(x, y), 1));
	}
}
void unionf(int x, int y, int& cnt) {
	x = findf(x), y = findf(y);
	if (x == y) return;
	cnt++;
	if (depth[x] < depth[y]) {
		uf[x] = y;
		stk.emplace_back(make_pair(make_pair(x, y), 0));
	}
	else if (depth[x] > depth[y]) {
		uf[y] = x;
		stk.emplace_back(make_pair(make_pair(y, x), 0));
	}
	else {
		uf[x] = y;
		depth[y]++;
		stk.emplace_back(make_pair(make_pair(x, y), 1));
	}
}

int color[400001];

int N, M, K, Q;
pair<int, int> edges[400000];
vector<pair<int, int>> evec;
int ans[400000];
vector<pair<pair<int, int>, int>> qvec;

bool ecomp(pair<int, int>& p1, pair<int, int>& p2) {
	return color[p1.first] < color[p2.first] || (color[p1.first] == color[p2.first] && color[p1.second] < color[p2.second]);
}
bool eequal(pair<int, int>& p1, pair<int, int>& p2) {
	return (color[p1.first] == color[p2.first]) && (color[p1.second] == color[p2.second]);
}
bool qcomp(pair<pair<int, int>, int>& p1, pair<pair<int, int>, int>& p2) {
	return ecomp(p1.first, p2.first);
}

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

	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) uf[i] = i;

	for (int i = 0; i < M; i++) cin >> edges[i].first >> edges[i].second;
	for (int i = 1; i <= N; i++) cin >> color[i];
	for (int i = 0; i < M; i++) {
		if (color[edges[i].first] == color[edges[i].second]) unionf(edges[i].first, edges[i].second);
		else {
			if (color[edges[i].first] > color[edges[i].second]) swap(edges[i].first, edges[i].second);
			evec.emplace_back(edges[i]);
		}
	}
	sort(evec.begin(), evec.end(), ecomp);

	cin >> Q;
	for (int i = 0; i < Q; i++) {
		int x, y; cin >> x >> y;
		if (color[x] == color[y]) ans[i] = (findf(x) == findf(y)) ? 1 : 0;
		else {
			if (color[x] > color[y]) swap(x, y);
			qvec.emplace_back(make_pair(make_pair(x, y), i));
		}
	}
	sort(qvec.begin(), qvec.end(), qcomp);

	int esize = evec.size(), qsize = qvec.size();
	int eidx = 0, qidx = 0;
	while (eidx < esize && qidx < qsize) {
		auto& e = evec[eidx]; auto& q = qvec[qidx];
		if (ecomp(e, q.first)) eidx++;
		else if (ecomp(q.first, e)) qidx++;
		else {
			int cnt = 0;
			while (eidx < esize && eequal(e, evec[eidx])) {
				unionf(evec[eidx].first, evec[eidx].second, cnt);
				eidx++;
			}
			while (qidx < qsize && eequal(q.first, qvec[qidx].first)) {
				ans[qvec[qidx].second] = (findf(qvec[qidx].first.first) == findf(qvec[qidx].first.second)) ? 1 : 0;
				qidx++;
			}
			while (cnt--) {
				auto& lglg = stk.back();
				uf[lglg.first.first] = lglg.first.first;
				if (lglg.second) depth[lglg.first.second]--;
				stk.pop_back();
			}
		}
	}

	for (int i = 0; i < Q; i++) cout << ans[i] << '\n';
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24451번 문제인 飴 2 (Candies 2)이다.
문제는 아래 링크를 확인하자.

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

N개의 사탕이 일렬로 놓여있을 때, 어떤 K개의 연속한 사탕을 살펴도 2개를 넘지 않는 사탕만을 골라 고른 사탕의 맛있는 정도의 총합을 최대화시키는 문제이다.

dp[i][j]를 (마지막으로 고른 두 개의 사탕의 인덱스가 i와 j인 경우의 사탕의 맛있는 정도의 총합의 최댓값)으로 정의하자. (단, i < j)

이 때, dp[i][j]는 1 이상 j-K 이하의 정수 k에 대하여 max(dp[k][i]) + arr[j]로 표현할 수 있음을 관찰하자. 단, 1 이상 j-K 이하의 정수가 존재하지 않는다면 dp[i][j]는 arr[i] + arr[j]로 계산하자. 위 식에서 k의 역할은 "i 이전에 먹은 사탕의 위치 후보"이다.

max(dp[k][i])를 매번 직접 계산하는 것은 오래 걸리므로 이 또한 별도의 메모이제이션을 이용해 시간복잡도를 감소시켜주자.

위 점화관계를 이용하는 것으로 문제를 O(N^2)에 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N, K;
ll arr[3001];
ll dp[3001][3001];
ll dpdp[3001][3001];
bool visited[3001][3001];

ll func(int q, int i) {
	if (q <= 0) return 0LL;
	if (visited[q][i]) return dpdp[q][i];
	visited[q][i] = 1;
	return dpdp[q][i] = max(func(q - 1, i), dp[q][i]);
}

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

	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> arr[i];

	ll ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) {
			if (j <= K || i == 1) dp[i][j] = arr[i] + arr[j];
			else dp[i][j] = func(min(j - K, i - 1), i) + arr[j];
			ans = max(ans, dp[i][j]);
		}
	}

	cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24450번 문제인 国土分割 (Land Division)이다.
문제는 아래 링크를 확인하자.

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

가로선과 세로선을 동시에 그어 국토분할이 제대로 이루어진 경우를 생각해보면, 각 분할된 칸 안에 적힌 수의 합이 각각 같은 상황이라는 의미이므로 가로선만으로 분할된 국토 및 세로선만으로 분할된 국토들도 각 분할에 적힌 수의 합이 같게 된다. 즉, 가로선과 세로선을 동시에 그어 국토분할이 이루어지는 경우의 수는 가로선만으로 분할할 수 있는 방법들과 세로선만으로 분할할 수 있는 방법들의 조합만을 살펴 실제로 분할이 이루어지는지를 확인해보는 것으로 계산해낼 수 있게 된다.

따라서, 가로선만을 긋는 방법과 세로선만을 긋는 방법들을 먼저 찾아내고 두 방법의 조합별로 선을 그었을 때 분할이 제대로 이루어지는지를 체크하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int R, C;
ll board[51][51];
ll rsum[51], csum[51], total = 0;
vector<vector<int>> rpartition, cpartition;

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

	cin >> R >> C;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			ll& x = board[r][c];
			cin >> x;
			rsum[r] += x, csum[c] += x, total += x;
		}
	}

	for (int k = 1; k <= R; k++) { // row들을 k개로 partition
		if (total % k) continue;
		ll val = total / k;
		ll psum = 0;
		bool chk = 1;
		vector<int> partition;
		for (int r = 1; r <= R; r++) {
			psum += rsum[r];
			if (psum > val) {
				chk = 0;
				break;
			}
			else if (psum == val) {
				partition.emplace_back(r);
				psum = 0;
			}
		}

		if (chk) rpartition.emplace_back(partition);
	}
	for (int k = 1; k <= C; k++) { // col들을 k개로 partition
		if (total % k) continue;
		ll val = total / k;
		ll psum = 0;
		bool chk = 1;
		vector<int> partition;
		for (int c = 1; c <= C; c++) {
			psum += csum[c];
			if (psum > val) {
				chk = 0;
				break;
			}
			else if (psum == val) {
				partition.emplace_back(c);
				psum = 0;
			}
		}

		if (chk) cpartition.emplace_back(partition);
	}

	int ans = 0;
	for (auto& rp : rpartition) {
		for (auto& cp : cpartition) {
			int rsize = rp.size(), csize = cp.size();
			int k = rsize * csize;
			if (total % k) continue;

			ll val = total / k;
			bool chk = 1;
			int oldr = 1;
			for (auto& r : rp) {
				int oldc = 1;
				for (auto& c : cp) {
					ll tmp = 0;
					for (int rr = oldr; rr <= r; rr++) {
						for (int cc = oldc; cc <= c; cc++) {
							tmp += board[rr][cc];
						}
					}
					if (tmp != val) chk = 0;
					oldc = c + 1;
				}
				oldr = r + 1;
			}
			if (chk) ans++;
		}
	}

	cout << ans - 1;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24449번 문제인 カーペット (Carpet)이다.
문제는 아래 링크를 확인하자.

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

주어진 카펫을 각 칸을 노드로 가지고, 변이 맞닿아있으면서 색이 서로 다른 칸 사이에 에지가 있는 그래프로 생각하자.

이 때, 좌상단의 칸에서 우하단의 칸까지의 최단경로는 위 그래프에서 BFS를 돌려보는 것으로 구할 수 있다.

좌상단의 칸에서 우하단까지 도달할 수 없는 경우 -1을 출력해주자.

아래는 제출한 소스코드이다.

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

int R, C;
string board[500];
int dist[500][500];
bool visited[500][500];
int dr[4] = { 1,0,-1,0 };
int dc[4] = { 0,1,0,-1 };

void bfs() {
	dist[0][0] = 1;
	queue<pair<int, int>> que;
	que.push(make_pair(0, 0));
	visited[0][0] = 1;

	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (-1 < rr && rr < R && -1 < cc && cc < C) {
				if (board[r][c] == board[rr][cc] || visited[rr][cc]) continue;
				visited[rr][cc] = 1;
				dist[rr][cc] = dist[r][c] + 1;
				que.push(make_pair(rr, cc));
			}
		}
	}
}

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> board[r];

	bfs();

	cout << dist[R - 1][C - 1] - 1 << '\n';
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24448번 문제인 図書館 2 (Library 2)이다.
문제는 아래 링크를 확인하자.

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

비타로가 책을 관리하는 방식은 stack 자료구조와 동일하다는 점을 관찰하자.

따라서, 문자열을 담는 stack을 이용하는 것으로 문제를 간단히 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int Q;
stack<string> stk;

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

	cin >> Q;
	while (Q--) {
		string s; cin >> s;
		if (s == "READ") {
			cout << stk.top() << '\n';
			stk.pop();
		}
		else stk.push(s);
	}
}