취미로 코딩하기

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

이번에 볼 문제는 백준 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;
}

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

이번에 볼 문제는 백준 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);
}

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

이번에 볼 문제는 백준 2620번 문제인 직각다각형의 면적 구하기이다.
문제는 아래 링크를 확인하자.

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

먼저, 구현을 편하게 하기 위해 주어진 도형을 각 점과 선의 "두께"를 1로 늘려 새로 그리자. 시간 제한과 메모리 제한을 생각하지 않는다면, 새로 그린 도형의 (도형의 바깥을 제외한) 각 영역에 대하여 행 또는 열이 다른 직선의 연장선에 포함되지 않은 칸들의 개수의 최댓값을 구하는 것으로 문제를 해결할 수 있을 것이다.

시간 제한과 메모리 제한을 통과하기 위해 각 점들의 좌표를 1000 이하의 정수로 줄이고, 각 칸의 너비와 높이가 줄어들기 전에 얼마였는지를 기록하는 방식을 이용하자. 이 때 각 영역의 칸의 개수를 세는 과정은 각 칸의 너비와 높이를 곱한 값의 합을 구하는 것으로 바뀐다. 다른 직선의 연장선에 해당하는 칸의 경우 그 직선의 방향에 따른 높이 또는 너비를 0으로 계산하면 별다른 예외처리 없이 이를 구현해낼 수 있음을 확인하자.

위와 같이 구현할 경우 시간복잡도는 $O(N^2)$이 되고, 이는 문제를 해결하기에 충분한 시간복잡도이다.

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

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

int N;
int R[1000], C[1000];
int dR[1000], dC[1000];
int compr_R[10001], compr_C[10001];
pair<int, int> points[1000];

int board[1001][1001];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
int dfs(int r, int c) {
	board[r][c] = 1;
	int ret = dR[r] * dC[c];
	for (int i = 0; i < 4; i++) {
		int rr = r + dr[i], cc = c + dc[i];
		if (rr<0 || rr>N || cc<0 || cc>N || board[rr][cc]) continue;
		ret += dfs(rr, cc);
	}

	return ret;
}

bool comp(pair<int, int>& p1, pair<int, int>& p2) {
	if (p1.second != p2.second) return p1.second < p2.second;
	return p1.first < p2.first;
}

int ans;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int& r = R[i], & c = C[i]; cin >> r >> c;
		points[i] = make_pair(r, c);
	}

	sort(R, R + N);
	for (int i = 0, idxR = 0; i < N; i++) {
		if (!compr_R[R[i]]) {
			if (i) dR[idxR * 2] = R[i] - R[i - 1];
			compr_R[R[i]] = idxR++ * 2 + 1;
		}
	}

	sort(C, C + N);
	for (int i = 0, idxC = 0; i < N; i++) {
		if (!compr_C[C[i]]) {
			if (i) dC[idxC * 2] = C[i] - C[i - 1];
			compr_C[C[i]] = idxC++ * 2 + 1;
		}
	}

	for (int i = 0; i < N; i++) {
		points[i].first = compr_R[points[i].first];
		points[i].second = compr_C[points[i].second];
	}

	sort(points, points + N);
	for (int i = 0; i < N; i += 2) {
		int r = points[i].first, c1 = points[i].second, c2 = points[i + 1].second;
		if (c1 > c2) swap(c1, c2);
		for (int c = c1; c <= c2; c++) {
			board[r][c] = 1;
		}
	}

	sort(points, points + N, comp);
	for (int i = 0; i < N; i += 2) {
		int r1 = points[i].first, r2 = points[i + 1].first, c = points[i].second;
		if (r1 > r2) swap(r1, r2);
		for (int r = r1; r <= r2; r++) {
			board[r][c] = 1;
		}
	}

	dfs(0, 0);

	for (int r = 0; r <= N; r++) {
		for (int c = 0; c <= N; c++) {
			if (!board[r][c]) ans = max(ans, dfs(r, c));
		}
	}

	cout << ans;
}