취미로 코딩하기

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

이번에 볼 문제는 백준 13703번 문제인 물벼룩의 생존확률이다.
문제는 아래 링크를 확인하자.

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

주어진 확률표기의 분모는 위와 아래의 나열로 가능한 경우의 수와 같은 2^N이므로, 구하는 값 S는 물벼룩이 수면 아래에서 N초동안 움직이는 경우의 수와 같다.

물벼룩이 t초에 수면아래 d 위치에 있을 경우의 수는 (물벼룩이 t-1초에 수면 아래 d+1위치에 있을 경우의 수) + (물벼룩이 t-1초에 수면 아래 d-1위치에 있을 경우의 수)로 계산할 수 있다. (단, d+1>0 이다.) 이 점화식을 이용하여 물벼룩이 N초에 수면 아래 d 위치에 있을 경우의 수들을 각각 구하고 이들을 합쳐 문제를 해결하자.

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

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

int K, N;
ll dp[64][128];

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

	cin >> K >> N;

	dp[0][K] = 1;

	for (int t = 1; t <= N; t++) {
		for (int d = 1; d < 127; d++) {
			dp[t][d] = dp[t - 1][d - 1] + dp[t - 1][d + 1];
		}
	}

	ll ans = 0;
	for (int d = 1; d < 127; d++) ans += dp[N][d];
	
	if (K == 0) cout << 0;
	else cout << ans;
}

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

이번에 볼 문제는 백준 13702번 문제인 이상한 술집이다.
문제는 아래 링크를 확인하자.

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

만약 막걸리를 x씩 분배한다면 막걸리를 받을 수 있는 사람은 "(각 주전자의 막걸리 용량) / x"값들의 총합과 같을 것이다. 이 때 x가 커지면 막걸리를 받을 수 있는 사람의 수는 단조감소하므로, 막걸리를 받을 수 있는 사람이 K 이상이 되게 하는 최대의 x를 이분탐색을 통해 계산해낼 수 있게 된다.

이를 이용해 문제를 해결하자.

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

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

ll N, K;
ll arr[10000];

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> arr[i];
	ll L = 0, R = 2147483647;
	while (L < R) {
		ll tmp = 0;
		ll mid = (L + R) / 2 + 1;
		for (int i = 0; i < N; i++) {
			tmp += arr[i] / mid;
		}

		if (tmp < K) R = mid - 1;
		else L = mid;
	}

	cout << L;
}

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

이번에 볼 문제는 백준 13701번 문제인 중복 제거이다.
문제는 아래 링크를 확인하자.

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

메모리제한이 없었다면 단순하게 방문여부만을 확인하는 크기 33554432의 bool 배열을 만들어 간단히 해결할 수 있었을 것이다.

위 배열의 각 원소는 방문했는지 안했는지의 여부만을 저장하면 되므로 1비트로도 충분히 정보를 담을 수 있다는 점을 관찰하자. 이를 이용해 33554432개의 비트를 이용해 메모리를 압축하고 문제를 해결하자.

별해로, vector<bool>의 경우 gcc가 각 자료를 1비트로 저장하게끔 메모리최적화를 해주므로 단순히 vector<bool>을 이용하는 것으로도 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int arr[1048576];

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

	int x;
	while (cin >> x) {
		int cell = x / 32, i = x % 32;
		if (arr[cell] & (1 << i)) continue;
		arr[cell] |= (1 << i);
		cout << x << ' ';
	}
}

아래는 vector<bool>을 이용한 별해이다.

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

vector<bool> arr(33554432);

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

	int x;
	while (cin >> x) {
		if (!arr[x]) {
			cout << x << ' ';
			arr[x] = 1;
		}
	}
}

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

이번에 볼 문제는 백준 13700번 문제인 완전 범죄이다.
문제는 아래 링크를 확인하자.

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

문제의 주어진 상황은 각 건물 i를 노드로 생각하고, i번 노드에서 i+F번 노드로, i번 노드에서 i-B번 노드로 향하는 방향간선이 있는 방향그래프로 모델링할 수 있다. 단, i번째 건물이 경찰서인 경우 없는 노드 취급하고, 범위를 벗어난(i+F>N 또는 i-B<1) 노드로 이동하는 에지 또한 없는 에지 취급하자.

위 방향그래프의 S번 노드에서 D번 노드까지의 최단거리를 BFS를 이용해 구하는 것으로 문제를 해결할 수 있다.

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

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

int N, S, D, F, B, K;

int dist[100001];

void bfs() {
	dist[S] = 1;
	queue<int> que;
	que.push(S);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		if (cur + F <= N && dist[cur + F] == 0) {
			dist[cur + F] = dist[cur] + 1;
			que.push(cur + F);
		}
		if (cur - B > 0 && dist[cur - B] == 0) {
			dist[cur - B] = dist[cur] + 1;
			que.push(cur - B);
		}
	}
}

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

	cin >> N >> S >> D >> F >> B >> K;
	while (K--) {
		int x; cin >> x;
		dist[x] = -1;
	}

	bfs();

	if (dist[D] == 0) cout << "BUG FOUND";
	else cout << dist[D] - 1;
}

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

이번에 볼 문제는 백준 13699번 문제인 점화식이다.
문제는 아래 링크를 확인하자.

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

주어진 점화식을 반복문을 이용하여 그대로 구현해주자.

재귀적으로 작동하는 함수와 dp를 이용하여 문제를 해결해도 좋을 것이다.

답이 32비트 정수로 표현 가능한 범위를 넘을 수 있음에 유의하자.

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

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

ll N;
ll dp[36];

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

	dp[0] = 1;
	for (ll i = 1; i < 36; i++) {
		for (ll j = 0; j < i; j++) dp[i] += dp[j] * dp[i - j - 1];
	}

	cin >> N;
	cout << dp[N];
}

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

이번에 볼 문제는 백준 13698번 문제인 Hawk eyes이다.
문제는 아래 링크를 확인하자.

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

주어진 문자열을 읽고 문자별로 swap을 이용하여 주어진 두 컵에 담긴 내용물을 바꾸는 것을 반복해 문제를 해결하자.

이 과정에서 switch문을 이용하면 구현을 편하게 할 수 있다.

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

#include <iostream>
#include <utility>
#include <string>
using namespace std;

int arr[5] = { 0,1,0,0,2 };

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

	string s; cin >> s;
	for (auto& l : s) {
		switch (l) {
		case 'A':swap(arr[1], arr[2]); break;
		case 'B':swap(arr[1], arr[3]); break;
		case 'C':swap(arr[1], arr[4]); break;
		case 'D':swap(arr[2], arr[3]); break;
		case 'E':swap(arr[2], arr[4]); break;
		case 'F':swap(arr[3], arr[4]); break;
		}
	}

	for (int i = 1; i < 5; i++) {
		if (arr[i] == 1) cout << i << '\n';
	}
	for (int i = 1; i < 5; i++) {
		if (arr[i] == 2) cout << i << '\n';
	}
}