취미로 코딩하기

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

이번에 볼 문제는 백준 10195번 문제인 Underwater Trip이다.
문제는 아래 링크를 확인하자.

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

잠수정이 움직일 때마다(즉 1초 단위로) 현재 잠수정이 터널의 천장, 바닥 또는 stalagmite와 충돌했는지의 여부를 계산해 문제를 해결하자. stalagmite와의 충돌 여부는 잠수정이 위치한 행과 stalagmite의 높이의 합과 터널의 높이의 값을 적절하게 비교하는 것으로 판단할 수 있다.

이 문제의 경우 주어지는 입력에 문제 해결에 필요하지 않은 문자열이 많이 포함되어 있다. 글쓴이는 이러한 문자열들을 대충 받아넘길 xx 변수를 만들어 필요없는 입력을 전부 xx로 받는 식으로 코드를 작성했다.

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

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

int T;
int R, C, stal, seq, tall, dist;
string xx;

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

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case: " << t << '\n';
		cin >> xx >> xx >> R >> xx >> C >> stal >> xx;
		vector<int> stalagmite(C + 1);
		while (stal--) {
			cin >> tall >> xx >> xx >> dist >> xx >> xx;
			stalagmite[dist] = max(stalagmite[dist], tall);
		}

		cin>> seq >> xx;

		while (seq--) {
			bool chk = 1;
			string s; cin >> s;
			int r = 0, c = 0;
			for (auto& l : s) {
				c++;
				if (l == 'v') r++;
				else if (l == '^') r--;

				if (r < 0) {
					cout << "Sequence " << s << " Crashed into tunnel ceiling\n";
					chk = 0;
					break;
				}
				else if (r >= R) {
					cout << "Sequence " << s << " Crashed into tunnel floor\n";
					chk = 0;
					break;
				}
				else if (r + 1 + stalagmite[c] > R) {
					cout << "Sequence " << s << " Crashed into stalagmite\n";
					chk = 0;
					break;
				}
			}

			if (chk) cout << "Sequence " << s << " Reached end of tunnel\n";
		}
	}
}

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

이번에 볼 문제는 백준 10194번 문제인 Aligned Calender이다.
문제는 아래 링크를 확인하자.

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

입력으로 주어진 년이 윤년인지 여부는 (1) 먼저 해당 년이 4로 나누어떨어지는지 확인하고 (2) 만약 해당 년이 100으로도 나누어떨어진다면 400으로도 나누어떨어지는지 확인하는 것으로 판단할 수 있다.

입력으로 주어지는 년이 윤년이 아니라는 가정 하에 입력으로 주어진 날짜가 몇 번째 일인지를 먼저 계산하고, 윤년이라면 3월 이후의 날들의 경우 1을 더해주자. 이를 28일을 한 달로 잡아 새로운 날짜를 계산해 문제를 해결할 수 있다.

문제에 주어진 각 달의 일수를 복사 및 붙여넣기해 배열을 만드는 것으로 구현할 때의 귀찮음을 덜어보자.

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

#include <iostream>
using namespace std;

int T;
int days[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int Y, M, D;

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

	cin >> T;
	while (T--) {
		cin >> Y >> M >> D;
		int ansM = 1, ansD = D;
		for (int m = 0; m < M; m++) ansD += days[m];
		if (Y % 4 == 0 && (Y % 100 || Y % 400 == 0) && M > 2) ansD++;
		while (ansD > 28) ansD -= 28, ansM++;

		if (ansM < 14) cout << Y << '/' << M << '/' << D << " became " << Y << '/' << ansM << '/' << ansD << '\n';
		else cout << Y << '/' << M << '/' << D << " became a HOLIDAY\n";
	}
}

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

이번에 볼 문제는 백준 28214번 문제인 크림빵이다.
문제는 아래 링크를 확인하자.

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

'빵을 N개씩 읽어 해당 N개의 빵이 들어있는 묶음이 판매가능한지 확인하는 작업'을 K번 반복하는 것으로 문제를 해결하자.

위 작업은 다음과 같이 해낼 수 있다: N개의 빵의 입력은 크림이 들어있는 빵은 1으로, 들어있지 않은 빵은 0으로 주어지므로 이 수들을 합해 N개의 빵 가운데 크림이 들어있는 빵의 개수를 계산해낼 수 있다. 그 값을 N에서 빼 크림이 들어있지 않은 빵의 개수를 구하고, 이 값을 P와 비교해 지금 확인중인 빵의 묶음이 판매가능한지 판단하자.

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

#include <iostream>
using namespace std;

int N, K, P;
int ans;

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

	cin >> N >> K >> P;
	while (N--) {
		int cnt = 0;
		for (int k = 0; k < K; k++) {
			int x; cin >> x;
			cnt += x;
		}

		if (K - cnt < P) ans++;
	}

	cout << ans;
}

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

이번에 볼 문제는 백준 17103번 문제인 골드바흐 파티션이다.
문제는 아래 링크를 확인하자.

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

100만을 넘는 소수는 주어지는 짝수의 합을 구성하는 소수로 쓰일 수 없으므로, 100만 이하의 모든 수에 대해 각 수가 소수인지 아닌지를 알 수 있는 에라토스테네스의 체를 구하자.

테스트케이스가 최대 100개로 적으므로, 각 테스트할 수 \(x\)에 대하여 합이 \(x\)가 되는 모든 \(a \leq b\)인 양의 정수쌍 \(a\)와 \(b\)에 대하여 각각이 소수가 되는 경우가 몇 가지인지를 세어 문제를 해결하자. 각 테스트는 최대 50만가지 경우를 확인해보는 것으로 답을 구할 수 있으므로 이는 문제를 해결하기에 충분한 방법이다.

2를 제외한 소수는 모두 홀수이므로 4를 제외한 모든 짝수의 합을 구성하는 두 소수는 홀수임을 이용해 아래의 제출 코드와 같은 약간의 최적화를 할 수 있다.

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

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

int sieve[1000001];
int T;

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

	sieve[1] = 1;
	for (int i = 2; i < 1000; i++) {
		if (sieve[i]) continue;
		for (int j = i * i; j < 1000000; j += i) sieve[j] = 1;
	}

	cin >> T;
	while (T--) {
		int ans = 0;
		int x; cin >> x;

		for (int i = 3; i * 2 <= x; i += 2) {
			if (sieve[i] || sieve[x - i]) continue;
			ans++;
		}
		if (x == 4) ans = 1;

		cout << ans << '\n';
	}
}

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

이번에 볼 문제는 백준 28073번 문제인 PSAT 특별과정이다.
문제는 아래 링크를 확인하자.

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

가장 적은 '문제'를 푸는 경로는 BFS를 이용해서 간단하게 구해낼 수 있다. 이 중 사전순으로 가장 빠른 경로를 찾으려면 어떻게 해야할까?

모든 '문제'가 갖는 가중치가 서로 다르다면 bfs 과정에서 각 노드에서 다음 노드를 큐(queue)에 담을 때 가중치가 증가하는 순서대로 담는 것으로 문제를 해결할 수 있을 것이다. 이와 같이 탐색하면 탐색 과정에서 나오는 같은 길이의 경로들끼리 비교했을 때 먼저 나오는 경로가 사전순으로 앞서게 되기 때문이다.

그러나 이 문제에서는 각 '문제'가 갖는 가중치에 중복이 있으므로 이에 유의해야 한다. 문자 S를 출력하게 되는 문제와 연결되어 있는 가중치가 같은 서로 다른 두 노드 A1과 A2, 그리고 가중치가 B>C인 두 노드 B와 C가 있는 경우를 생각해보자. 탐색과정에서 A1을 SA2보다 먼저 방문하고 A1에서 다음으로 탐색할 수 있는 후보가 B, A2에서 다음으로 탐색할 수 있는 후보가 C뿐이라면 위와 같은 방식으로 탐색을 하면 SA1B가 SA2C보다 먼저 등장하게 된다. 그러나 SA2C가 SA1B보다 사전순으로 앞서므로 이 방법을 수정하지 않으면 문제의 답을 올바르게 낼 수 없다.

당장은 같은 가중치를 가져 사전순에 영향을 주지 않지만 이후의 탐색 과정에서 가중치가 역전되어 사전순에 영향을 줄 수 있는 경우가 문제이므로, 이를 해결하기 위해 BFS 탐색 중 현재 노드에서 방문할 수 있는 중복된 가중치를 갖는 노드가 존재하는 경우를 만날 때마다 해당 노드들을 합쳐 새로운 노드를 만들어주자. 이와 같이 구현하면 위와 같은 문제를 피해 올바른 답을 구해낼 수 있다.

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

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

int N, M; char S, E;
vector<int> G[1000002];
int prv[1000002];
string L;

bool comp(int& x, int& y) {
	return L[x] < L[y];
}

queue<int> que;
void bfs() {
	que.push(N + 1); prv[N + 1] = -1;
	for (int i = 1; i <= N; i++) {
		if (L[i] == S) G[N + 1].emplace_back(i);
	}

	for (int i = 0; i <= N; i++) sort(G[i].begin(), G[i].end(), comp);

	while (!que.empty()) {
		int cur = que.front(); que.pop();
		if (L[cur] == E) {
			string ans = "";
			while (prv[cur] > 0) {
				ans += L[cur];
				cur = prv[cur];
			}

			while (!ans.empty()) {
				cout << ans.back();
				ans.pop_back();
			}
			return;
		}
		int old = 0; char oldchar = ' '; set<int> st;
		for (auto& nxt : G[cur]) {
			if (prv[nxt]) continue;
			prv[nxt] = cur;
			if (L[nxt] != oldchar) {
				if (old) {
					set<int> stst;
					for (auto& x : st) {
						for (auto& xx : G[x]) {
							stst.insert(xx);
						}
					}
					G[old].clear();
					for (auto& xxx : stst) G[old].emplace_back(xxx);
					sort(G[old].begin(), G[old].end(), comp);
					st.clear();
					que.push(old);
				}
				old = nxt, oldchar = L[nxt];
			}

			st.insert(nxt);
		}

		if (old) {
			set<int> stst;
			for (auto& x : st) {
				for (auto& xx : G[x]) {
					stst.insert(xx);
				}
			}
			G[old].clear();
			for (auto& xxx : stst) G[old].emplace_back(xxx);
			sort(G[old].begin(), G[old].end(), comp);
			st.clear();
			que.push(old);
		}
	}

	cout << "Aaak!";
}

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

	cin >> N >> M >> S >> E >> L;
	L = " " + L + "*";
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}
	
	bfs();
}

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

이번에 볼 문제는 백준 28072번 문제인 K512에서 피자 먹기이다.
문제는 아래 링크를 확인하자.

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

psum[i]를 1번부터 i번까지의 피자조각의 무게의 합을 K로 나눈 나머지라 정의하자. 이 배열은 i를 1부터 N까지 차례대로 늘려나가면서 psum[i-1]의 값을 참조해(psum[0]=0으로 정의하자) \(O(N)\)으로 계산할 수 있다.

L번 조각부터 R번 조각까지로 이루어진 피자 조각을 [L,R]이라 부르자. 이 때, 피자 조각 [L,R]의 무게가 K의 배수라면 psum[L-1]과 psum[R]의 값이 같아야 함을 관찰할 수 있다. 또한, psum[x]와 psum[y]의 값이 같다면 피자 조각 [x+1,y] 및 [y+1,x]의 무게 또한 K의 배수가 됨을 관찰할 수 있다.

위의 관찰을 이용하면 문제의 답은 가능한 k값에 대하여 psum의 값이 k이고 1 이상 N 이하인 i값의 개수의 최댓값이 됨을 알 수 있다. 이를 구하는 코드를 작성해 문제를 해결하자.

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

#include <iostream>
using namespace std;

int N, K;
int arr[1000001];
int cnt[100001];

int ans;

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

	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
		arr[i] += arr[i - 1];
		arr[i] %= K;
		cnt[arr[i]]++;
	}

	for (int i = 0; i < K; i++) ans = max(ans, cnt[i]);

	cout << ans;
}