취미로 코딩하기

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

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

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

이러한 형태의 문제는 첫번째 수열을 두번 연속 이어붙인 수열에 두번째 수열이 존재하는지를 확인하는 것으로 문제를 해결할 수 있다.

이는 KMP 알고리즘을 이용해 선형시간에 해결가능하다.

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

#include <iostream>
using namespace std;

int N;
int A[300001];
int pi[300001];

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i + N + 1];
	for (int i = 0; i < N; i++) A[i + 2 * N + 1] = A[i + N + 1];
	for (int i = 0; i < N; i++) cin >> A[i];
	A[N] = 2000000007;

	bool chk = 0;
	for (int i = 0; i <= 3 * N; i++) {
		int idx = i;
		while (idx > 0) {
			if (A[pi[idx - 1]] == A[i]) break;
			idx = pi[idx - 1];
		}
		if (idx == 0) pi[i] = 0;
		else pi[i] = pi[idx - 1] + 1;

		if (pi[i] == N) chk = 1;
	}

	if (chk) cout << "YES";
	else cout << "NO";
}

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

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

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

주어진 지도 위에서, 두 역 사이를 상하좌우 움직임으로 잇는 경로 중 경로에 적힌 수의 총합이 가장 작은 경로의 그 총합 값을 찾는 문제이다. (단, -1이 적힌 칸은 지날 수 없다.)

이러한 총합 값의 최솟값은 다익스트라(dijkstra) 알고리즘을 이용해 계산해낼 수 있다. 이를 통해 문제를 해결하자.

주어지는 두 역의 위치에 -1이 있을 수도 있으므로 이에 주의하자.

또한 주어지는 좌표가 (행,열) 순이 아닌 (열,행) 순으로 주어짐에 유의하자.

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

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

int N;
int sR, sC, eR, eC;
ll board[400][400];
ll dist[400][400];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void dijkstra() {
	dist[sR][sC] = board[sR][sC] + 1;
	priority_queue<pair<ll, pair<int,int>>> pq;
	pq.push(make_pair(-board[sR][sC] - 1, make_pair(sR, sC)));
	while (!pq.empty()) {
		ll d = -pq.top().first; int r = pq.top().second.first, c = pq.top().second.second; pq.pop();
		if (d > dist[r][c]) continue;
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= N || cc < 0 || cc >= N || board[rr][cc] < 0) continue;
			if (dist[rr][cc] == 0 || d + board[rr][cc] < dist[rr][cc]) {
				dist[rr][cc] = d + board[rr][cc];
				pq.push(make_pair(-dist[rr][cc], make_pair(rr, cc)));
			}
		}
	}
}

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

	cin >> N >> sC >> sR >> eC >> eR;
	sR--, sC--, eR--, eC--;

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> board[r][c];
		}
	}

	if (board[sR][sC] < 0) cout << -1;
	else {
		dijkstra();
		cout << dist[eR][eC] - 1;
	}
}

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

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

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

주어지는 점들 중 가장 먼 두 점 사이의 거리를 묻는 문제이다. 이는 convex hull 위에서의 rotating calipers 테크닉을 이용해 해결할 수 있음이 잘 알려져있다. 이를 이용해 문제를 해결하자.

(글쓴이는 적용하지는 않았지만) 이에 더해 주어진 좌표의 범위가 충분히 작다는 점을 이용해 convex hull을 구성하는 꼭짓점의 후보를 추리는 것으로 속도 향상을 꾀할 수도 있다.

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;

int N;
pll points[1000000];
vector<pll> upperhull; // leftmost x의 lowermost y부터 rightmost x의 uppermost y까지
vector<pll> lowerhull;

int CCW(pll& A, pll& B, pll& C) {
	ll ccw = (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
	if (ccw > 0) return 1;
	else if (ccw < 0) return -1;
	else return 0;
}

void andrew_algorithm() {
	sort(points, points + N);

	//upperhull
	for (int i = 0; i < N; i++) {
		auto& cur = points[i];
		int cursize = upperhull.size();
		while (cursize > 1) {
			auto& L = upperhull[cursize - 2], & M = upperhull[cursize - 1];
			if (CCW(L, M, cur) != -1) upperhull.pop_back(), cursize--;
			else break;
		}
		upperhull.emplace_back(cur);
	}

	//lowerhull
	for (int i = 0; i < N; i++) {
		auto& cur = points[i];
		int cursize = lowerhull.size();
		while (cursize > 1) {
			auto& L = lowerhull[cursize - 2], & M = lowerhull[cursize - 1];
			if (CCW(L, M, cur) != 1) lowerhull.pop_back(), cursize--;
			else break;
		}
		lowerhull.emplace_back(cur);
	}
}

ll dfunc(pll& p1, pll& p2) {
	return (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second);
}

void rotating_calipers() {
	int u = 0, uend = upperhull.size(), l = lowerhull.size() - 1;
	ll mx = dfunc(upperhull[u], lowerhull[l]);
	while (u < uend - 1 && l > 0) {
		if (upperhull[u].first == upperhull[u + 1].first) u++;
		else if (lowerhull[l].first == lowerhull[l - 1].first) l--;
		else {
			ll dx1 = upperhull[u + 1].first - upperhull[u].first, dy1 = upperhull[u + 1].second - upperhull[u].second;
			ll dx2 = lowerhull[l].first - lowerhull[l - 1].first, dy2 = lowerhull[l].second - lowerhull[l - 1].second;

			if (dy1 * dx2 > dx1 * dy2) u++;
			else l--;
		}
		mx = max(mx, dfunc(upperhull[u], lowerhull[l]));
	}

	while (u < uend - 1) {
		u++;
		mx = max(mx, dfunc(upperhull[u], lowerhull[l]));
	}
	while (l > 0) {
		l--;
		mx = max(mx, dfunc(upperhull[u], lowerhull[l]));
	}

	cout << mx;
}

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

	cin >> N;
	int trash; cin >> trash;
	for (int i = 0; i < N; i++) cin >> points[i].first >> points[i].second;

	andrew_algorithm();
	rotating_calipers();
}

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

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

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

한번에 꿀을 M씩 가져오는 것이 최선의 수이므로, M씩 가져올 수 있는 횟수를 미리 구해두자. 또한, 이와 같이 시행했을 때 각 나무에 남는 꿀의 양을 구해두자.

한번에 꿀을 M씩 가져올 수 있는 횟수가 K 이상이면 한번에 꿀을 M씩 K번 가져오는 것으로 문제를 해결할 수 있다.

그렇지 않은 경우, 남은 꿀 중 한번에 가장 많이 가져올 수 있는 나무부터 순서대로 꿀을 가져오는 것으로 문제를 해결할 수 있다.

K가 충분히 클 경우 K번 모두를 굳이 움직일 필요는 없다는 점을 고려해 위의 내용을 구현하자.

문제의 답이 32비트 정수 자료형을 넘을 수 있으므로 이에 유의해 구현하자.

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

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

ll N, M, K;
ll arr[200000];

ll fullcnt;

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

	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		ll& cur = arr[i];
		cin >> cur;

		fullcnt += cur / M; cur %= M;
	}

	sort(arr, arr + N);

	if (K <= fullcnt) cout << K * M;
	else {
		ll ans = fullcnt * M;
		K = min(N, (K - fullcnt));
		for (int i = 0; i < K; i++) ans += arr[N - 1 - i];

		cout << ans;
	}
}

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

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

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

주어지는 배드민턴 경기의 득점순서를 보고, 각 경기를 직접 시뮬레이션을 돌려 문제를 해결하자.

각 문자 또한 아스키코드 숫자가 할당되어있다는 점을 이용하여 아래와 같이 배열을 이용해 구현할 수도 있다.

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

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

int cnt[128];
int wincnt[128];

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

	string s; cin >> s;
	for (auto& l : s) {
		if (l == 'A') {
			cnt['A']++;
			if (cnt['A'] == 21) {
				cout << cnt['A'] << '-' << cnt['B'] << '\n';
				wincnt['A']++;
				cnt['A'] = cnt['B'] = 0;
			}
		}
		else {
			cnt['B']++;
			if (cnt['B'] == 21) {
				cout << cnt['A'] << '-' << cnt['B'] << '\n';
				wincnt['B']++;
				cnt['A'] = cnt['B'] = 0;
			}
		}
	}

	if (wincnt['A'] == 2) cout << 'A';
	else cout << 'B';
}