취미로 코딩하기

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

이번에 볼 문제는 백준 2250번 문제인 트리의 높이와 너비이다.
문제는 아래 링크를 확인하자.

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

중위순회(inorder traversal)을 이용해 주어지는 이진트리의 노드들을 x좌표순으로 나열해나가면서, 각 깊이의 최소 x좌표와 최대 x좌표를 관리하는 코드를 작성해 문제를 해결하자.

주어진 트리의 루트노드는 "어떤 노드의 자식노드로 쓰인 적이 없는 노드"를 찾는 것으로 빠르게 발견해낼 수 있다.

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

#include <iostream>
using namespace std;

int idx = 1;
int N, root;
int G[10001][2];
int level[10001][2];
bool is_child[10001];

void dfs(int cur, int lv) {
	if (G[cur][0] > 0) dfs(G[cur][0], lv + 1);
	if (level[lv][0] == 0) level[lv][0] = level[lv][1] = idx++;
	else level[lv][1] = idx++;
	if (G[cur][1] > 0) dfs(G[cur][1], lv + 1);
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		int& l = G[x][0], & r = G[x][1]; cin >> l >> r;
		if (l > 0) is_child[l] = 1;
		if (r > 0) is_child[r] = 1;
	}

	for (int i = 1; i <= N; i++) {
		if (!is_child[i]) root = i;
	}
	
	dfs(root, 1);

	int mx = -1, lv = -1;
	for (int i = 1; i <= N; i++) {
		if (!level[i][0]) break;
		int diff = level[i][1] - level[i][0] + 1;
		if (diff > mx) mx = diff, lv = i;
	}

	cout << lv << ' ' << mx;
}

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

이번에 볼 문제는 백준 2618번 문제인 경찰차이다.
문제는 아래 링크를 확인하자.

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

dp[x][y]를 (1번 경찰차가 마지막으로 처리한 사건이 x, 2번 경찰차가 마지막으로 처리한 사건이 y)인 경우의 최소 이동거리라 하자. 이 때 dp값은 이 값은 x>y+1인 경우 dp[x-1][y] + (1번 경찰차가 x-1에서 x까지 이동한 거리), y>x+1인 경우 dp[x][y-1] + (2번 경찰차가 y-1에서 y까지 이동한 거리)로 계산할 수 있다. x=y+1인 경우에는 dp[i][y]의 최솟값(단, i는 y미만), y = x+1인 경우에는 dp[x][i]의 최솟값(단, i는 x 미만)이 된다. x와 y가 같은 경우는 존재할 수 없다.

위의 점화식을 이용해 문제를 해결하자. 어떤 경찰차를 실제로 움직였는지 역추적하는 과정은 위 계산을 진행하면서 각 과정의 최적해가 어떤 이전 단계로부터 왔는지를 별도의 배열에 저장하는 것으로 간단히 구현할 수 있다.

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

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

int N, W;
int dp[1001][1001]; // dp[x][y]: 1번 경찰차가 마지막으로 처리한 사건은 x, 2번 경찰차가 마지막으로 처리한 사건은 y
pair<int,int> backtrack[1001][1001];
bool visited[1001][1001];
int R1[1001], C1[1001], R2[1001], C2[1001];

int dist1(int i, int j) {
	return abs(R1[i] - R1[j]) + abs(C1[i] - C1[j]);
}

int dist2(int i, int j) {
	return abs(R2[i] - R2[j]) + abs(C2[i] - C2[j]);
}

int func(int x, int y) {
	int& ret = dp[x][y];
	if (visited[x][y]) return ret;
	visited[x][y] = 1;

	if (x > y + 1) ret = func(x - 1, y) + dist1(x - 1, x), backtrack[x][y] = make_pair(x - 1, y);
	else if (x + 1 < y) ret = func(x, y - 1) + dist2(y - 1, y), backtrack[x][y] = make_pair(x, y - 1);
	else {
		ret = 2000000007;
		if (x > y) {
			for (int i = 0; i < y; i++) {
				int val = func(i, y) + dist1(i, x);
				if (val < ret) ret = val, backtrack[x][y] = make_pair(i, y);
			}
		}
		else {
			for (int i = 0; i < x; i++) {
				int val = func(x, i) + dist2(i, y);
				if (val < ret) ret = val, backtrack[x][y] = make_pair(x, i);
			}
		}
	}

	return ret;
}

int ans = 2000000007, ansx, ansy;
vector<int> stk;

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

	cin >> N >> W;
	for (int i = 1; i <= W; i++) {
		cin >> R1[i] >> C1[i];
	}
	for (int i = 1; i <= W; i++) R2[i] = R1[i], C2[i] = C1[i];
	R1[0] = C1[0] = 1, R2[0] = C2[0] = N;
	
	dp[1][0] = dist1(0, 1), dp[0][1] = dist2(0, 1);
	visited[1][0] = visited[0][1] = 1;
	backtrack[1][0] = backtrack[0][1] = make_pair(0, 0);

	for (int i = 0; i < W; i++) {
		int val = func(i, W);
		if (val < ans) ans = val, ansx = i, ansy = W;
		val = func(W, i);
		if (val < ans) ans = val, ansx = W, ansy = i;
	}
	
	while (ansx + ansy) {
		if (ansx > ansy) stk.emplace_back(1);
		else stk.emplace_back(2);

		int nxtx = backtrack[ansx][ansy].first, nxty = backtrack[ansx][ansy].second;
		ansx = nxtx, ansy = nxty;
	}

	cout << ans << '\n';
	while (!stk.empty()) {
		cout << stk.back() << '\n';
		stk.pop_back();
	}
}

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

이번에 볼 문제는 백준 2116번 문제인 주사위 쌓기이다.
문제는 아래 링크를 확인하자.

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

맨 아래의 주사위의 밑면을 하나 고정한다면, 쌓은 주사위의 각 층에 사용될 수 있는 옆면의 수는 네 종류로 전부 고정됨을 관찰하자. 이 관찰을 이용하면 각 주사위의 밑면을 고정하는 여섯 경우에 대한 탐색을 통해 문제를 간단히 해결할 수 있다.

이를 구현하는 것은 어렵지 않다. (1) 밑면에 있던 수를 마주보는 면에 있는 수로 바꾸고 (2) 앞에서 나온 두 수를 제외한 수 중 최댓값을 더하는 두 작업을 반복하는 코드를 작성하는 것으로 구현할 수 있기 때문이다.

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

#include <iostream>
using namespace std;

int N;
int psum[6];
int uface[6] = { 1,2,3,4,5,6 };

int mx;

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

	cin >> N;
	while (N--) {
		int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f;
		for (int i = 0; i < 6; i++) {
			int& cur = uface[i];
			if (cur == a) cur = f, psum[i] += max(max(b, c), max(d, e));
			else if (cur == b) cur = d, psum[i] += max(max(a, c), max(e, f));
			else if (cur == c) cur = e, psum[i] += max(max(a, b), max(d, f));
			else if (cur == d) cur = b, psum[i] += max(max(a, c), max(e, f));
			else if (cur == e) cur = c, psum[i] += max(max(a, b), max(d, f));
			else cur = a, psum[i] += max(max(b, c), max(d, e));
		}
	}

	for (int i = 0; i < 6; i++) mx = max(mx, psum[i]);

	cout << mx;
}

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

이번에 볼 문제는 백준 2615번 문제인 오목이다.
문제는 아래 링크를 확인하자.

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

오목 게임의 한 장면이 주어질 때, 승패가 결정났는지를 먼저 판단하고, 결정났다면 연속으로 다섯개 놓여있는 돌의 위치가 어디인지를 추가로 출력하는 문제이다.

바둑판 위에서 일렬로 다섯 개의 돌이 연속으로 위에 놓일 수 있는 모든 가능한 방법에 대해 (1) 해당 다섯 위치에 같은 돌이 올려져 있고, (2) 그 연장선에 해당하는 위치에 그 같은 돌이 올려져있지 않은지를 확인해 승패가 결정났는지를 판단할 수 있다.

돌이 다섯 개 연속으로 놓인 곳의 위치를 출력할 때, 가장 위쪽에 놓인 돌이 우선순위가 아닌 가장 왼쪽에 놓인 돌의 위치를 우선적으로 출력해야함에 유의하자.

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

#include <iostream>
using namespace std;

int board[21][21];

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

	for (int r = 1; r < 20; r++) {
		for (int c = 1; c < 20; c++) {
			cin >> board[r][c];
		}
	}

	for (int r = 1; r < 20; r++) {
		for (int c = 1; c < 16; c++) {
			if (board[r][c] && board[r][c] == board[r][c + 1] && board[r][c + 1] == board[r][c + 2] && board[r][c + 2] == board[r][c + 3] && board[r][c + 3] == board[r][c + 4] && board[r][c-1]!=board[r][c] && board[r][c+4] != board[r][c+5]) {
				cout << board[r][c] << '\n';
				cout << r << ' ' << c;
				return 0;
			}
		}
	}

	for (int r = 1; r < 16; r++) {
		for (int c = 1; c < 20; c++) {
			if (board[r][c] && board[r][c] == board[r + 1][c] && board[r + 1][c] == board[r + 2][c] && board[r + 2][c] == board[r + 3][c] && board[r + 3][c] == board[r + 4][c] && board[r - 1][c] != board[r][c] && board[r + 4][c] != board[r + 5][c]) {
				cout << board[r][c] << '\n';
				cout << r << ' ' << c;
				return 0;
			}
		}
	}

	for (int r = 1; r < 16; r++) {
		for (int c = 1; c < 16; c++) {
			if (board[r][c] && board[r][c] == board[r + 1][c + 1] && board[r + 1][c + 1] == board[r + 2][c + 2] && board[r + 2][c + 2] == board[r + 3][c + 3] && board[r + 3][c + 3] == board[r + 4][c + 4] && board[r - 1][c - 1] != board[r][c] && board[r + 4][c + 4] != board[r + 5][c + 5]) {
				cout << board[r][c] << '\n';
				cout << r << ' ' << c;
				return 0;
			}
		}
	}

	for (int r = 5; r < 20; r++) {
		for (int c = 1; c < 16; c++) {
			if (board[r][c] && board[r][c] == board[r - 1][c + 1] && board[r - 1][c + 1] == board[r - 2][c + 2] && board[r - 2][c + 2] == board[r - 3][c + 3] && board[r - 3][c + 3] == board[r - 4][c + 4] && board[r + 1][c - 1] != board[r][c] && board[r - 4][c + 4] != board[r - 5][c + 5]) {
				cout << board[r][c] << '\n';
				cout << r << ' ' << c;
				return 0;
			}
		}
	}

	cout << 0;
}

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

이번에 볼 문제는 백준 2617 문제인 구슬 찾기이다.
문제는 아래 링크를 확인하자.

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

주어진 구슬들 중, 자신보다 더 무거운게 확실한(주어진 조건들을 이용해 직접 추론 가능한) 구슬의 개수 또는 더 가벼운게 확실한 구슬의 개수가 N의 절반을 넘는 구슬의 개수를 세는 것으로 문제를 해결할 수 있다. 이러한 경우 해당 구슬의 무게가 전체의 중간이 될 수 없음은 자명하다. 그렇지 않은 경우 위상정렬 등을 이용하면 해당 구슬을 가운데 차례에 위치하게끔 하는 방법을 쉽게 얻을 수 있다. (구체적인 방법 서술은 생략한다.)

이를 구하기 위해, 주어진 무게관계들을 이용해 A가 B보다 더 무거움에 대응되는 방향에지로 만들어진 그래프와 A가 B보다 더 가벼움에 대응되는 방향에지로 만들어진 그래프를 만들자. 이 때, 각 그래프에서 어떤 노드 x로부터 다른 노드 y로 가는 경로가 존재한다는 것은 x와 y 사이의 무게 사이에 (그래프의 종류에 따른) 관계가 있음을 의미함을 관찰하자. 따라서 이와 같은 그래프를 이용하면 각 노드에서 이동할 수 있는 노드의 개수를 세는 것으로 문제를 해결할 수 있게 된다.

전체 구슬의 개수가 충분히 적으므로, 해당 값을 구하기 위해 각 노드를 출발점으로 하는 탐색을 일일이 시도하는 것으로도 문제를 충분히 해결할 수 있다.

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

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

int N, M;
vector<int> G1[100], G2[100];
int visited[100];

int func1(int x) {
	memset(visited, 0, sizeof(visited));
	int ret = 0;
	queue<int> que;
	que.push(x);
	visited[x] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& nxt : G1[cur]) {
			if (visited[nxt]) continue;
			ret++, que.push(nxt);
			visited[nxt] = 1;
		}
	}

	return ret;
}

int func2(int x) {
	memset(visited, 0, sizeof(visited));
	int ret = 0;
	queue<int> que;
	que.push(x);
	visited[x] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& nxt : G2[cur]) {
			if (visited[nxt]) continue;
			ret++, que.push(nxt);
			visited[nxt] = 1;
		}
	}

	return ret;
}

int ans;

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

	cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		G1[x].emplace_back(y);
		G2[y].emplace_back(x);
	}

	for (int i = 1; i <= N; i++) {
		if (func1(i) > N / 2 || func2(i) > N / 2) ans++;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 1983번 문제인 숫자 박스이다.
문제는 아래 링크를 확인하자.

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

0을 제외한 주어진 숫자 박스의 위쪽 행의 숫자들을 차례대로 저장한 배열을 A, 아래쪽 행의 숫자들을 차례대로 저장한 배열을 B라 하자(1-based). 그리고 dp[n][a][b]를 A배열의 첫 a개의 수와 B배열의 첫 b개의 수를 길이 n의 숫자박스에 채워넣을 때의 가능한 최댓값으로 정의하자. 이 때, 구하고자 하는 값은 dp[N][cntA][cntB]가 된다. (단, cntA는 A의 길이, cntB는 B의 길이이다.)

dp[n][a][b]가 나타내는 상황에서, 숫자박스의 마지막 칸은 다음과 같은 네 경우 중 한가지 방법으로 구성된다:

(1) 위쪽 행에는 A배열의 a번째 수, 아래쪽 행에는 B배열의 b번째 수가 들어간다.

(2) 위쪽 행에는 A배열의 a번째 수, 아래쪽 행에는 0이 들어간다.

(3) 위쪽 행에는 0, 아래쪽 행에는 B배열의 b번째 수가 들어간다.

(4) 위쪽 행에는 0, 아래쪽 행에도 0이 들어간다.

위와 같이 숫자박스를 구성해나갈 경우, 남은 숫자박스의 길이(n)으로 모든 수를 채워 숫자박스를 구성할 수 있는지의 여부(n보다 a가 더 커지거나 하는 등)와 그 때의 최댓값 등을 다시 dp값을 이용해 나타내면 점화식을 얻을 수 있다. 이 점화식을 잘 구현해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N;
int A[401], B[401];
int cntA, cntB;

int dp[401][401][401];
bool visited[401][401][401];

int func(int n, int a, int b) {
	int& ret = dp[n][a][b];
	if (visited[n][a][b]) return ret;
	visited[n][a][b] = 1;
	ret = -1000000007;

	if (a && b) ret = max(ret, func(n - 1, a - 1, b - 1) + A[a] * B[b]);
	if (a && n > b) ret = max(ret, func(n - 1, a - 1, b));
	if (b && n > a) ret = max(ret, func(n - 1, a, b - 1));
	if (n > a && n > b) ret = max(ret, func(n - 1, a, b));
	return ret;
}

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

	for (int i = 0; i < 401; i++) visited[i][0][0] = 1;

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		if (x) A[++cntA] = x;
	}
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		if (x) B[++cntB] = x;
	}

	cout << func(N, cntA, cntB);
}