취미로 코딩하기

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

이번에 볼 문제는 백준 12181번 문제인 Googlander (Large)이다.
문제는 아래 링크를 확인하자.

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

이미 방문한 칸 및 격자 바깥의 칸은 방문할 수 없고, 회전 방향이 고정되어있음을 잘 이용해 문제를 해결해 보자.

\(C\)의 값이 1이라면 Googlander은 첫 행 끝까지 걸어 올라가고 행동을 멈추는 움직임만을 할 수 있으므로 움직임의 경우의 수는 단 하나임을 알 수 있다.

\(C\)의 값이 1이 아니라면, Googlander은 첫 행부터 마지막 행까지 중 하나의 행까지 올라간 다음 90도 회전해 앞으로 전진할 수 있다. 이 때 \(k\)번째 행까지 Googlander가 올라갔다면 90도 회전해 한 칸 전진한 이후의 움직임은 \(C-1\)행 \(R-(k-1)\)열로 구성된 격자에서의 Googlander의 움직임의 경우의 수와 같은 가짓수의 움직임이 가능함을 알 수 있다. 

위 두 관찰을 이용해 점화식을 구성하여 문제를 해결하자.

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

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

int R, C;
ll dp[26][26];
ll func(ll r, ll c) {
	ll &ret = dp[r][c];
	if (ret) return ret;
	if (c == 1) return ret = 1;
	for (int rr = 1; rr <= r; rr++) {
		ret += func(c - 1, rr);
	}
	return ret;
}

void solve() {
	cin >> R >> C;
	cout << func(R, C) << '\n';
}

int T;

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

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case #" << t << ": ";
		solve();
	}
}

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

이번에 볼 문제는 백준 2128번 문제인 마지막 조별 시합이다.
문제는 아래 링크를 확인하자.

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

\(N\)명 중 일부를 골랐을 때, \(D\) 문제중 풀 수 있는 문제의 집합으로 나올 수 있는 경우의 수는 많아야 \(2^D\)가지임을 확인하자. 이러한 각 문제의 집합 중 원소가 \(K\)개 이하(풀 수 있는 문제의 수가 \(K\)개 이하)인 경우에 대하여 각 경우 포함할 수 있는 최대 인원을 \(N\)명을 직접 전부 살피는 식으로 확인해 문제를 해결하자.

특히, 집합의 원소가 \(K\)개인 경우만 살펴도 그 이하인 경우의 최대인원보다 항상 더 큰 값을 얻게 되므로 \(K\)개인 경우만 살펴도 충분히 문제를 해결할 수 있다. 이렇게만 살펴도 실제 그 집합의 모든 문제를 다 풀 수 있는 인원구성이 나오지 않는 경우(즉, 집합의 원소가 \(K\)개 미만인경우) 또한 전부 살피는 것과 같은 효과를 보임을 확인하자.

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

#include <iostream>
using namespace std;

int N, M, K;
int A[1000];
int ans;

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

	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		int X; cin >> X;
		int &val = A[i];
		while (X--) {
			int x; cin >> x;
			val |= (1 << (x - 1));
		}
	}
	M = (1 << M);
	for (int i = 0; i < M; i++) {
		if (__builtin_popcount(i) == K) {
			int cnt = 0;
			for (int n = 0; n < N; n++) {
				if ((A[n] & i) == A[n]) cnt++;
			}
			ans = max(ans, cnt);
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 20914번 문제인 QWERTY 자판이다.
문제는 아래 링크를 확인하자.

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

주어진 그림의 자판을 각 키를 정점으로, 서로 인접한 관계에 있는 키의 쌍의 관계를 에지로 갖는 그래프로 모델링하면 어떤 키를 누른 뒤 다음 키를 누를 때까지 걸리는 이동시간을 이 그래프 위에서의 최단거리를 이용해 구할 수 있게 된다.

정점의 개수가 충분히 적으므로 글쓴이는 Floyd-Warshall 알고리즘을 이용해 각 키 사이의 이동거리를 전처리하려 문제를 해결하였다. 각 키를 시작점으로 하는 BFS 등을 이용해도 문제를 충분히 해결할 수 있을 것이다.

인접한 두 키 정보를 기록할 때 특히 신경써서 빠진 정보가 없게끔 유의하자.

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

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

int dist[128][128];
int Q, N, ans;
string s;

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

	memset(dist, 0x3f, sizeof(dist));
	for (char i = 'A'; i <= 'Z'; i++) dist[i][i] = 0;
	dist['Q']['W'] = dist['W']['E'] = dist['E']['R'] = dist['R']['T'] = dist['T']['Y'] = dist['Y']['U'] = dist['U']['I'] = dist['I']['O'] = dist['O']['P'] = 1;
	dist['A']['S'] = dist['S']['D'] = dist['D']['F'] = dist['F']['G'] = dist['G']['H'] = dist['H']['J'] = dist['J']['K'] = dist['K']['L'] = 1;
	dist['Z']['X'] = dist['X']['C'] = dist['C']['V'] = dist['V']['B'] = dist['B']['N'] = dist['N']['M'] = 1;
	dist['Q']['A'] = dist['A']['Z'] = dist['W']['S'] = dist['S']['X'] = dist['E']['D'] = dist['D']['C'] = dist['R']['F'] = dist['F']['V'] = dist['T']['G'] = dist['G']['B'] = dist['Y']['H'] = dist['H']['N'] = dist['U']['J'] = dist['J']['M'] = dist['I']['K'] = dist['O']['L'] = 1;
	dist['W']['A'] = dist['E']['S'] = dist['S']['Z'] = dist['R']['D'] = dist['D']['X'] = dist['T']['F'] = dist['F']['C'] = dist['Y']['G'] = dist['G']['V'] = dist['U']['H'] = dist['H']['B'] = dist['I']['J'] = dist['J']['N'] = dist['O']['K'] = dist['K']['M'] = dist['P']['L'] = 1;

	for (char i = 'A'; i <= 'Z'; i++) {
		for (char j = 'A'; j <= 'Z'; j++) {
			if (dist[i][j] == 1) dist[j][i] = 1;
		}
	}

	for (char k = 'A'; k <= 'Z'; k++) {
		for (char i = 'A'; i <= 'Z'; i++) {
			for (char j = 'A'; j <= 'Z'; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	cin >> Q;
	while (Q--) {
		cin >> s; N = s.length(); ans = 0;
		for (int i = 0; i + 1 < N; i++) ans += dist[s[i]][s[i + 1]];
		cout << ans * 2 + N << '\n';
	}
}

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

이번에 볼 문제는 백준 22288번 문제인 Rainbow Road Race이다.
문제는 아래 링크를 확인하자.

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

343개의 각 fun location과 지금까지 어떤 색의 에지들을 경유해 지금의 location에 도착했는지(총 128가지 경우의 수)를 묶어 하나의 노드로 생각하면 주어진 문제는 가중치가 있는 그래프에서의 최단거리 문제로 볼 수 있다. 이는 dijkstra 알고리즘을 이용해 해결할 수 있다.

각 방문상태를 bitmask를 이용해 표현해 효율적으로 구현하자.

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

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

int N, M;
vector<pair<int, pair<int, int>>> G[344];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
int dist[344][128];
void dijkstra() {
	memset(dist, 0x3f, sizeof(dist));
	dist[1][0] = 0;
	pq.push(make_pair(0, make_pair(1, 0)));
	while (!pq.empty()) {
		int cur = pq.top().second.first, b = pq.top().second.second, d = pq.top().first; pq.pop();
		if (dist[cur][b] < d) continue;
		for (auto &p:G[cur]) {
			int nxt = p.first, dd = d + p.second.first, bb = b | p.second.second;
			if (dd < dist[nxt][bb]) dist[nxt][bb] = dd, pq.push(make_pair(dd, make_pair(nxt, bb)));
		}
	}
}

int ctoi[128];

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

	ctoi['R'] = 1, ctoi['O'] = 2, ctoi['Y'] = 4, ctoi['G'] = 8, ctoi['B'] = 16, ctoi['I'] = 32, ctoi['V'] = 64;

	cin >> N >> M;
	while (M--) {
		int x, y, d; char c; cin >> x >> y >> d >> c;
		G[x].emplace_back(make_pair(y, make_pair(d, ctoi[c])));
		G[y].emplace_back(make_pair(x, make_pair(d, ctoi[c])));
	}

	dijkstra();
	cout << dist[1][127];
}

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

이번에 볼 문제는 백준 2874번 문제인 검정 직사각형이다.
문제는 아래 링크를 확인하자.

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

격자 위에서의 두 겹치지 않는 직사각형은 (1)어떤 행방향 경계선을 기준으로 두 직사각형이 서로 다른 쪽에 존재하거나 (2)어떤 열방향 경계선을 기준으로 두 직사각형이 서로 다른 쪽에 존재한다. (물론 둘 모두에 해당할 수도 있다.) 따라서 문제의 답은 행방향 경계선으로 나누어 두 직사각형을 넣는 경우의 수와 열방향 경계선을 기준으로 나누어 두 직사각형을 넣는 경우의 수의 합에서 두 경계선 모두로 나누어 직사각형을 넣는 경우의 수를 빼는 것으로 구할 수 있다.

위 각각의 경우의 수는 각 칸을 기준으로 해당 칸을 좌상단, 좌하단, 우상단, 우하단 칸으로 갖는 경우의 수 및 그 값들의 적절한 2차원 누적합을 전처리한 후 스위핑하는 것으로 빠르게 계산할 수 있다. 글쓴이는 각 경우의 수를 스택을 이용한 히스토그램 문제 풀이법을 이용해 계산하였다. (이 문제에 히스토그램이 어디에 있는지 모르겠다면, 각 행을 기준으로 그 행의 밑바닥(?)에 붙어있는 위쪽 열방향으로 연속한 검정 칸모양을 그려보면 히스토그램과 같음을 알 수 있을 것이다. 이 아이디어는 의외로 곳곳에서 활용되므로 기억해두는 것이 좋다.)

10007로 나눈 나머지를 구하라는 조건을 놓쳐 몇 번 틀렸다(...). 항상 문제가 요구하는 것을 주의깊게 읽자.

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

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

int N;
char board[1002][1002];
int LU[1002][1002], RU[1002][1002], LD[1002][1002], RD[1002][1002];
int H[1002];

vector<pair<int, int>> stk; // {높이, 길이}
int ans;

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

	cin >> N; stk.reserve(N);
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			cin >> board[r][c];
		}
	}
	
	memset(H, 0, sizeof(H));
	for (int r = 1; r <= N; r++) {
		int psum = 0;
		stk.clear();
		for (int c = 1; c <= N; c++) {
			int &h = H[c];
			if (board[r][c] == 'C') h++;
			else h = 0;
			int len = 1;
			while (!stk.empty() && stk.back().first >= h) {
				len += stk.back().second;
				psum -= stk.back().first * stk.back().second;
				stk.pop_back();
			}
			psum += h * len;
			stk.emplace_back(make_pair(h, len));
			LU[r][c] = (max(psum - 1, 0) + LU[r - 1][c] + LU[r][c - 1] - LU[r - 1][c - 1]) % 10007;
		}
	}

	memset(H, 0, sizeof(H));
	for (int r = 1; r <= N; r++) {
		int psum = 0;
		stk.clear();
		for (int c = N; c > 0; c--) {
			int &h = H[c];
			if (board[r][c] == 'C') h++;
			else h = 0;
			int len = 1;
			while (!stk.empty() && stk.back().first >= h) {
				len += stk.back().second;
				psum -= stk.back().first * stk.back().second;
				stk.pop_back();
			}
			psum += h * len;
			stk.emplace_back(make_pair(h, len));
			RU[r][c] = (max(psum - 1, 0) + RU[r - 1][c] + RU[r][c + 1] - RU[r - 1][c + 1]) % 10007;
		}
	}

	memset(H, 0, sizeof(H));
	for (int r = N; r > 0; r--) {
		int psum = 0;
		stk.clear();
		for (int c = N; c > 0; c--) {
			int &h = H[c];
			if (board[r][c] == 'C') h++;
			else h = 0;
			int len = 1;
			while (!stk.empty() && stk.back().first >= h) {
				len += stk.back().second;
				psum -= stk.back().first * stk.back().second;
				stk.pop_back();
			}
			psum += h * len;
			stk.emplace_back(make_pair(h, len));
			RD[r][c] = (max(psum - 1, 0) + RD[r + 1][c] + RD[r][c + 1] - RD[r + 1][c + 1]) % 10007;
		}
	}

	memset(H, 0, sizeof(H));
	for (int r = N; r > 0; r--) {
		int psum = 0;
		stk.clear();
		for (int c = 1; c <= N; c++) {
			int &h = H[c];
			if (board[r][c] == 'C') h++;
			else h = 0;
			int len = 1;
			while (!stk.empty() && stk.back().first >= h) {
				len += stk.back().second;
				psum -= stk.back().first * stk.back().second;
				stk.pop_back();
			}
			psum += h * len;
			stk.emplace_back(make_pair(h, len));
			LD[r][c] = (max(psum - 1, 0) + LD[r + 1][c] + LD[r][c - 1] - LD[r + 1][c - 1]) % 10007;
		}
	}

	for (int r = 1; r < N; r++) {
		ans += (RU[r][1] - RU[r - 1][1]) * RD[r + 1][1];
		ans %= 10007;
	}
	for (int c = 1; c < N; c++) {
		ans += (LD[1][c] - LD[1][c - 1]) * RD[1][c + 1];
		ans %= 10007;
	}
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			ans -= (LU[r][c] - LU[r - 1][c] - LU[r][c - 1] + LU[r - 1][c - 1]) * RD[r + 1][c + 1];
			ans -= (LD[r][c] - LD[r + 1][c] - LD[r][c - 1] + LD[r + 1][c - 1]) * RU[r - 1][c + 1];
			ans %= 10007;
		}
	}
	ans %= 10007;
	if (ans < 0) ans += 10007;
	cout << ans;
}

#랜덤 마라톤 · 코스 9 H번

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

이번에 볼 문제는 백준 14953번 문제인 Game Map이다.
문제는 아래 링크를 확인하자.

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

더 작은 차수의 노드에서 더 큰 차수의 노드로만 이동이 가능하므로, 주어진 그래프에서의 이동 가능한 관계를 그래프로 나타내면 이는 DAG를 이룸을 알 수 있다.

따라서 주어진 문제는 DAG에서의 최장거리를 구하는 문제로 볼 수 있고, 이는 위상정렬을 통해 쉽게 해결할 수 있다. 이를 구현해 문제를 해결하자.

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

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

int N, K;
vector<int> G[100000];
int deg[100000], idg[100000];
int dist[100000], mx;
vector<pair<int, int>> E;
queue<int> que;
void bfs() {
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		mx = max(mx, dist[cur]);
		for (auto &nxt : G[cur]) {
			idg[nxt]--;
			dist[nxt] = max(dist[nxt], dist[cur] + 1);
			if (!idg[nxt]) que.push(nxt);
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	while (K--) {
		int x, y; cin >> x >> y;
		E.emplace_back(make_pair(x, y));
		deg[x]++, deg[y]++;
	}

	for (auto &p : E) {
		if (deg[p.first] > deg[p.second]) G[p.second].emplace_back(p.first), idg[p.first]++;
		else if (deg[p.first] < deg[p.second]) G[p.first].emplace_back(p.second), idg[p.second]++;
	}
	for (int i = 0; i < N; i++) {
		if (!idg[i]) {
			que.push(i);
			dist[i] = 1;
		}
	}
	bfs();
	cout << mx;
}