취미로 코딩하기

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

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

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

이 문제는 분할정복(Divide&Conquer)으로 해결할 수 있다.

구간 [L,R]에 속하는 Kuching이 먹을 수 있는 생선토막 [l,r]들은 (L<R일 경우) mid = (L+R)/2에 대하여 (1) [L,mid]와 [mid+1,R] 양쪽에 걸쳐있거나 (2) [L,mid] 또는 [mid+1,R]에 완전히 포함되거나 정확히 둘중 하나를 만족시킨다. 따라서 구하는 경우의 수는 (1)의 가짓수와 (2)의 가짓수를 합하는 것으로 계산해낼 수 있다. 즉, (1)의 값을 답에 더하고, 각 (2)의 경우에 대한 부분문제를 다시 해결하는 것을 반복하는 것으로 문제를 해결할 수 있다.

(1)의 경우의 수는 prefix sum 배열과 정렬 및 투포인터 테크닉을 이용해 빠르게 구할 수 있다.

이 알고리즘의 시간복잡도는 \(O(Nlg^2N)\)과 같다.

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

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

ll N, K;
ll arr[200000];
ll psumL[100000], psumR[100000];
ll ans;

void func(int L, int R) {
	if (L == R) {
		if (arr[L] >= K) ans++;
		return;
	}

	int mid = (L + R) / 2;
	ll sizeL = mid - L + 1, sizeR = R - mid;
	psumL[0] = arr[mid];
	for (int i = 1; i < sizeL; i++) psumL[i] = psumL[i - 1] + arr[mid - i];
	psumR[0] = arr[mid + 1];
	for (int i = 1; i < sizeR; i++) psumR[i] = psumR[i - 1] + arr[mid + 1 + i];

	sort(psumL, psumL + sizeL);
	sort(psumR, psumR + sizeR);
	
	ll idxL = sizeL - 1, idxR = 0;
	while (idxL > -1 && idxR < sizeR) {
		if (psumL[idxL] + psumR[idxR] < K) idxR++;
		else {
			ans += sizeR - idxR;
			idxL--;
		}
	}

	func(L, mid), func(mid + 1, R);
}

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

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> arr[i];

	func(0, N - 1);

	cout << ans;
}

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

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

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

X를 N 이하의 양의 정수의 부분집합 중 A[i]들의 집합과 B[i]들의 집합이 같게 하는 i들의 집합 중 minimal한(minimum이 아니다) 집합이라 하자. 이 때 이 X에 속한 인덱스들의 A[i]들을 B[i]와 같이 바꾸기 위해 총 (X의 원소의 개수) - 1회의 swap 연산이 필요하다는 점을 관찰할 수 있다.

이를 이용해 위와 같은 성질을 지닌 X의 개수를 구해 N에서 빼주는 것으로 문제를 해결할 수 있다.

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

#include <iostream>
using namespace std;

int N;
int arr[1000001];
int nxt[1000001];
bool visited[1000001];

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

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

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

	int ans = N;
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			int ii = i;
			while (!visited[ii]) {
				visited[ii] = 1;
				ii = nxt[ii];
			}
			ans--;
		}
	}

	cout << ans;
}

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

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

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

문제의 주어진 그래프는 {노드번호, 다음으로 사용할 수 있는 에지의 값}을 노드로 갖는 가중치 없는 방향그래프로 새로이 모델링할 수 있다. 이와 같은 모델링 위에서 주어진 문제는 {0,0}, {0,1}을 시작점으로 할 때 {N-1,0} 또는 {N-1,1}까지의 최단거리를 찾는 문제가 된다.

이와 같은 형태의 문제는 bfs를 이용하여 해결 가능하다.

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

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

int N, E;
vector<int> G[200000][2];
int dist[200000][2];

void bfs() {
	dist[0][0] = dist[0][1] = 1;
	queue<pair<int, int>> que;
	que.push(make_pair(0, 0));
	que.push(make_pair(0, 1));
	while (!que.empty()) {
		int x = que.front().first, w = que.front().second; que.pop();
		for (auto& nxt : G[x][w]) {
			if (dist[nxt][w ^ 1]) continue;
			dist[nxt][w ^ 1] = dist[x][w] + 1;
			que.push(make_pair(nxt, w ^ 1));
		}
	}
}

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

	cin >> N >> E;
	while (E--) {
		int x, y, w; cin >> x >> y >> w;
		G[x][w].emplace_back(y);
		G[y][w].emplace_back(x);
	}

	bfs();

	int& ans1 = dist[N - 1][0], & ans2 = dist[N - 1][1];
	if (ans1 && ans2) cout << min(ans1, ans2) - 1;
	else if (ans1) cout << ans1 - 1;
	else if (ans2) cout << ans2 - 1;
	else cout << -1;
}

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

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

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

주어지는 각 정수가 문제에서 요구하는 두 조건을 만족하는지를 확인하는 문제이다.

양의 정수 N이 K 이하의 수로 나누어지는지의 여부는 N이 K보다 작거나 같은지, 그리고 N이 \(min(K, \sqrt{N})\) 이하의 소수로 나누어지는지의 여부를 이용해 판단할 수 있다. 에라토스테네스의 체를 이용해 가능한 소수의 후보들을 미리 구해두고 문제를 해결하자.

같은 숫자가 네번 이상 연속으로 나오는지는 to_string을 이용해 주어진 수를 문자열로 가공해 판단하면 간단히 구현할 수 있다.

문제의 조건에 따라 1은 항상 조건을 만족시킴에 유의하자.

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

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

ll N, K;
bool sieve[100000];
vector<ll> primes;

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

	sieve[0] = sieve[1] = 1;
	for (ll i = 2; i < 100000; i++) {
		if (sieve[i]) continue;
		for (ll j = i * i; j < 100000; j += i) sieve[j] = 1;
	}

	for (ll i = 2; i < 100000; i++) {
		if (!sieve[i]) primes.emplace_back(i);
	}

	cin >> N >> K;
	while (N--) {
		bool chk = 1;
		ll x; cin >> x;
		if (x == 1) {
			cout << "YES\n";
			continue;
		}
		else if (x <= K) {
			cout << "NO\n";
			continue;
		}

		for (auto& p : primes) {
			if (p > K || p * p > x) break;
			if ((x % p) == 0) {
				chk = 0;
				break;
			}
		}

		char old = '?'; int combo = 0;
		string s = to_string(x);
		for (auto& l : s) {
			if (l == old) combo++;
			else {
				if (combo > 3) chk = 0;
				old = l, combo = 1;
			}
		}
		if (combo > 3) chk = 0;

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

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

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

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

주어진 N개의 문자열이 주어질 때, M개의 각 문자열이 N개의 문자열 중 하나와 같은지를 판단하는 문제이다. 이는 set을 이용하여 간단히 해결할 수 있다.

구체적으로, N개의 문자열을 set에 집어넣고, M개의 각 문자열이 set에 포함되어있는지를 확인해 문제를 해결하자.

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

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

int N, M, ans;
set<string> st;

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

	cin >> N;
	while (N--) {
		string s; cin >> s;
		st.insert(s);
	}

	cin >> M;
	while (M--) {
		string s; cin >> s;
		if (st.count(s)) ans++;
	}

	cout << ans;
}

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

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