취미로 코딩하기

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

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