취미로 코딩하기

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

이번에 볼 문제는 백준 27212번 문제인 미팅이다.
문제는 아래 링크를 확인하자.

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

dp[X][Y]를 A대학의 첫 X명의 학생와 B 대학의 첫 Y명의 학생들끼리 악수를 할 때의 만족도의 최댓값이라 하자.

이 때, 최댓값을 구성하는 악수 짝은 (1) A대학의 X번째 학생과 B대학의 Y번째 학생이 서로 악수를 하거나 (2) A대학의 X번째 학생과 B대학의 Y보다 작은 순서의 누군가가 서로 악수를 하거나 (3) A대학의 X보다 작은 순서의 누군가와 B대학의 Y가 서로 악수를 하는 셋 중 하나를 만족시켜야 함을 알 수 있다.

위의 각 경우를 dp[X][Y]를 이용한 식으로 나타내어 점화관계를 찾아내고 적절한 메모이제이션을 활용해 문제를 해결해주자.

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

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

ll N, M, C;
ll W[17][17];

int arrN[1001], arrM[1001];
ll dp[1001][1001];
ll func(int idxN, int idxM) {
	ll& ret = dp[idxN][idxM];
	if (ret) return ret;
	return ret = max(func(idxN - 1, idxM - 1) + W[arrN[idxN]][arrM[idxM]], max(func(idxN - 1, idxM), func(idxN, idxM - 1)));
}

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

	cin >> N >> M >> C;
	for (int r = 1; r <= C; r++) {
		for (int c = 1; c <= C; c++) {
			cin >> W[r][c];
		}
	}

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

	for (int r = 0; r <= N; r++) dp[r][0] = 1;
	for (int c = 0; c <= M; c++) dp[0][c] = 1;

	cout << func(N, M) - 1;
}

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

이번에 볼 문제는 백준 27211번 문제인 도넛 행성이다.
문제는 아래 링크를 확인하자.

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

주어진 도넛 행성 위에서의 움직임은 N행 M열로 구성된 격자판 위에서 N행의 다음 행은 1행이고 M열의 다음 열은 1열과 같은 움직임으로 나타낼 수 있음을 관찰하자.

위와 같은 관찰을 토대로, 주어진 N행M열의 배치를 숲이 아닌 칸을 노드로, 도넛 행성 위에서의 서로 인접한 숲이 아닌 칸의 관계를 에지로 하는 그래프로 생각하자. 이 때, 문제에서 구하고자 하는 값은 해당 그래프의 connected component의 개수와 같아지므로 그 개수를 세는 것으로 문제를 해결할 수 있다.

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

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

int R, C;
int board[1000][1000];
int ans;
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void bfs(int sr, int sc) {
	board[sr][sc] = 1;
	queue<pair<int, int>> que;
	que.push(make_pair(sr, sc));
	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 (rr < 0) rr = R - 1;
			else if (rr == R) rr = 0;
			if (cc < 0) cc = C - 1;
			else if (cc == C) cc = 0;

			if (!board[rr][cc]) {
				board[rr][cc] = 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++) {
		for (int c = 0; c < C; c++) {
			cin >> board[r][c];
		}
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c]) continue;
			bfs(r, c);
			ans++;
		}
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 27210번 문제인 신을 모시는 사당이다.
문제는 아래 링크를 확인하자.

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

각 석상의 인덱스를 1부터 N까지의 정수로 순서대로 부여하자. 구간 [0,k]에 속한 왼쪽을 향하는 석상의 수를 L[k], 오른쪽을 향하는 석상의 수를 R[k]라 하자. 이 때 구간 [x,y]에 속한 왼쪽을 향하는 석상의 수는 L[y]-L[x-1], 오른쪽을 향하는 석상의 수는 R[y]-R[x-1]로 나타낼 수 있음을 관찰할 수 있다.

위의 관찰로부터 구하는 값은 (R[y]-L[y]) - (R[x-1]-L[x-1])의 절댓값의 최댓값과 같다는 점을 알 수 있다. 따라서 R[k]-L[k]의 최댓값과 최솟값을 각각 구해 둘의 차를 구하는 것으로 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N;
int cnt = 0;
int mx = 0, mn = 0;

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

	cin >> N;
	while (N--) {
		int x; cin >> x;
		if (x == 1) cnt++;
		else cnt--;
		mx = max(mx, cnt), mn = min(mn, cnt);
	}

	cout << mx - mn;
}