취미로 코딩하기

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

이번에 볼 문제는 백준 25331번 문제인 Drop 7이다.
문제는 아래 링크를 확인하자.

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

문제에서 주어진 Drop 7 게임의 일부를 직접 구현해 시뮬레이션을 돌리는 문제이다.

글쓴이는 다음과 같은 과정을 구현해 문제를 해결했다.

(1) 각 열에 주어진 공을 집어넣는 시도를 한 번씩 한다. 아래부터는 열을 하나 정해 공을 넣은 상황이다.

(2) 각 행과 열을 둘러보면서, 이번 차례에 지워질 공이 무엇인지를 찾아내 별도의 배열에 기록한다.

(3) 지워질 공을 기록한 배열을 참조해, 이번 차례에 지워질 공들을 지운다. 이 과정에서 지워진 공이 있는지의 여부를 기록해둔다.

(4) 공들을 아래로 내린다.

(5) (3)에서 이번 차례에 지워진 공이 있었다면 (2)로 돌아간다.

(6) 남아있는 공의 개수를 센다.

(4)에서 내릴 공이 없더라도 지워진 공이 있었다면 (2)로 돌아가 확인해볼 필요가 있다는 점에 유의하자.

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

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

int K;
int original[7][7];
int board[7][7];
int deleted[7][7];
int ans = 1000000007;

void func(int col) {
	for (int r = 0; r < 7; r++) {
		for (int c = 0; c < 7; c++) board[r][c] = original[r][c];
	}
	for (int r = 6; r > -1; r--) {
		if (board[r][col]) continue;
		board[r][col] = K;
		break;
	}

	bool chk = 1;
	while (chk) {
		chk = 0;
		memset(deleted, 0, sizeof(deleted));

		for (int r = 0; r < 7; r++) {
			int cL = 0, combo = 0;
			for (int c = 0; c < 7; c++) {
				if (board[r][c]) combo++;
				else {
					for (int cc = cL; cc < c; cc++) {
						if (board[r][cc] == combo) deleted[r][cc] = 1;
					}
					cL = c + 1, combo = 0;
				}
			}
			for (int cc = cL; cc < 7; cc++) {
				if (board[r][cc] == combo) deleted[r][cc] = 1;
			}
		}
		for (int c = 0; c < 7; c++) {
			int rL = 0, combo = 0;
			for (int r = 0; r < 7; r++) {
				if (board[r][c]) combo++;
				else {
					for (int rr = rL; rr < r; rr++) {
						if (board[rr][c] == combo) deleted[rr][c] = 1;
					}
					rL = r + 1, combo = 0;
				}
			}
			for (int rr = rL; rr < 7; rr++) {
				if (board[rr][c] == combo) deleted[rr][c] = 1;
			}
		}
		
		for (int r = 0; r < 7; r++) {
			for (int c = 0; c < 7; c++) {
				if (deleted[r][c]) chk = 1, board[r][c] = 0;
			}
		}

		for (int c = 0; c < 7; c++) {
			for (int r = 6; r > -1; r--) {
				if (board[r][c]) {
					int rr = r + 1;
					while (rr < 7 && board[rr][c] == 0) {
						board[rr][c] = board[rr - 1][c];
						board[rr - 1][c] = 0;
						rr++;
					}
				}
			}
		}
	}

	int cnt = 0;
	for (int r = 0; r < 7; r++) {
		for (int c = 0; c < 7; c++) {
			if (board[r][c]) cnt++;
		}
	}
	ans = min(ans, cnt);
}

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

	for (int r = 0; r < 7; r++) {
		for (int c = 0; c < 7; c++) cin >> original[r][c];
	}
	cin >> K;

	for (int col = 0; col < 7; col++) func(col);

	cout << ans;
}

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

이번에 볼 문제는 백준 25330번 문제인 SHOW ME THE DUNGEON이다.
문제는 아래 링크를 확인하자.

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

마을의 방문 순서에 관계없이, 구할 마을을 고를 경우의 수는 2^20 = 1048576가지이다. 이 각각의 경우에 대해 각 집합에 들어있는 마을들을 전부 구하기에 체력이 충분한지 여부와 주민수의 합을 구해 문제를 해결하자.

마을들을 미리 정해뒀을 때, 공격력이 약한 몬스터가 있는 마을부터 greedy하게 방문하는 것이 체력을 가장 적게 소모하는 방법이된다. 총 V개의 마을을 방문할 때, 시루의 체력은 각 i에 대해 (i번째로 방문한 마을의 몬스터의 공격력) * (V - i)만큼 필요하다는 점을 이용하면 위의 방문순서가 최적임을 쉽게 증명할 수 있다.

위의 내용들을 이용해, 각 마을에 있는 몬스터의 공격력을 기준으로 마을들을 미리 정렬해두면 매번 새로 정렬할 필요 없이 완전탐색으로 문제를 간단히 해결할 수 있게 된다.

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

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

int N, K;
pair<int, int> p[20];

int asum, psum;
int ans = 0;

void func(int ith) {
	ans = max(ans, psum);
	if (ith < N) {
		func(ith + 1);
		int& A = p[ith].first, & P = p[ith].second;
		if (K >= asum + A) {
			asum += A;
			K -= asum;
			psum += P;
			func(ith + 1);
			psum -= P;
			K += asum;
			asum -= A;
		}
	}
}

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> p[i].first;
	for (int i = 0; i < N; i++) cin >> p[i].second;
	
	sort(p, p + N);

	func(0);

	cout << ans;
}

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

이번에 볼 문제는 백준 25332번 문제인 수들의 합 8이다.
문제는 아래 링크를 확인하자.

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

Ai-Bi를 새로운 수열 Ci로 정의하면, 주어진 문제는 Ci의 합이 0이 되는 구간 [L,R]의 개수를 세는 문제로 바꿔 생각할 수 있다.

위와 같이 문제를 바꾸면 이 문제는 2015번 문제(링크)과 같은 문제로 바뀌게 된다. 해당 글을 참고해 문제를 해결하자.

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

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

int N;
int arr[200000];
map<int, int> mp;
int psum = 0;
ll ans = 0;

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

	mp.insert(make_pair(0, 1));

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		arr[i] -= x;
	}

	for (int i = 0; i < N; i++) {
		psum += arr[i];
		if (mp.count(psum)) ans += mp[psum]++;
		else mp.insert(make_pair(psum, 1));
	}

	cout << ans;
}

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

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