본문 바로가기

알고리즘 문제풀이/USACO 문제 풀이

USACO 2020 US Open Contest [Bronze] 풀이

반응형

 

 

1. [BOJ 18880] Social Distancing I  Gold V

 

 

[문제 설명] 

 

일렬로 N개의 공간이 있고, 각 공간은 소가 들어있거나(1) 들어있지 않다(0). 그리고 빈 두 공간을 골라 소를 넣어주는데, 이때 소가 들어있는 두 공간 사이의 간격의 최솟값을 D라고 하면 D가 최대가 되어야 한다. 

 

[풀이]

 

Case work 문제이다. 경우들을 잘 처리해주어야 한다.

 

지금부터 말하는 '구간'은 소가 배정되어있지 않은 연속된 공간을 의미한다. 

우선, 가장 긴 구간에서 하나를 뽑아서 구간을 나눈 후, 다시 가장 긴 구간에서 하나를 뽑는 것이 최적일 것이라고 생각할 수 있다.

하지만 이 문제에서는 공간을 두 개 고르기 때문에 단순히 이 방식으로는 D를 최대로 만들지 못한다. 

예를 들어 1, 10, 13 번째에 소가 들어있다고 하자. 그러면 현재 D는 2가 되고, 최대 구간의 길이는 8이 된다.

따라서 1과 10의 중간에 해당하는 5(또는 6)에 소를 넣으면 1, 5, 10, 13이 되고, 사이의 가장 큰 간격은 4가 된다. 

그 다음 나머지 한 소를 5와 10의 중간인 7(또는 8)에 넣게 되면 1, 5, 7, 10, 13이 되고 D는 1이 되어버린다. 

과연 1이 답이 될 수 있을까? 

1과 10을 3등분하는 지점에 두 소를 한번에 배정해보자. 그러면 1, 4, 7, 10, 13이 되고, D는 2가 된다. 

 

따라서 한 구간을 3개로 나누는 경우가 두 구간을 각각 반으로 나누는 경우보다 더 좋을 수도 있다. 

또한, 양끝에 구간이 존재하는 경우에는 소를 제일 처음 또는 제일 끝에 배정하게 되면 구간이 1만큼만 줄어들면서 소를 배정할 수 있다. 

 

[소스 코드]

 

#include<bits/stdc++.h>
#define sz(x) (int)x.size()
using namespace std;
const int MAX = 2e9;
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int N; cin >> N;
	string s; cin >> s;
	int cnt = 0;
	priority_queue<int> pq;
	bool chk = false;
	vector<int> side;
	for (int i = 0; i < sz(s); i++) {
		if (s[i] == '0') cnt++;
		else {
			if (!chk) {
				if (cnt > 0) side.push_back(cnt);
				chk = true;
			}
			else {
				if (cnt > 0) pq.push(cnt);
			}
			cnt = 0;
		}
	}
	if (cnt > 0) side.push_back(cnt);
	if (!chk) {
		cout << N - 1;
		return 0;
	}
	int num = 2;
	for (int i : side) {
		if (pq.empty() || (pq.top() - 1) / 2 <= i - 1) {
			pq.push(i - 1);
			num--;
		}
	}
	if (num == 1) {
		pq.push((pq.top() - 1) / 2);
		pq.push(pq.top() / 2);
		pq.pop();
	}
	else if (num == 2) {
		int k = pq.top(); pq.pop();
		if (pq.empty()) {
			pq.push((k - 2) / 3);
		}
		else {
			if ((k - 2) / 3 > (pq.top() - 1) / 2) {
				pq.push((k - 2) / 3);
			}
			else {
				int k1 = pq.top();
				pq.push((k - 1) / 2); pq.push((k1 - 1) / 2);
			}
		}
	}
	int ans = MAX;
	while (!pq.empty()) {
		ans = min(ans, pq.top()); 
		pq.pop();
	}
	cout << ans+1;
}

 

 

2. [BOJ 18881] Social Distancing II  Silver V

 

 

[문제 설명]

 

일렬로 소가 서있고, 어떤 소는 감염되었고 어떤 소는 감염되지 않았다. 

그리고 감염된 소는 거리 R 이내에 있는 소들을 감염시킬 때, 제일 처음에 감염된 소의 수의 최솟값을 구하는 문제이다. 

 

[풀이]

 

먼저 소를 위치순으로 정렬을 한다. 

감염되지 않은 소들로부터 감염된 소까지의 최소 거리보다 R이 작아야 한다.

그리고, 가능한 값 중 최댓값을 R로 해야 처음에 감염된 소의 수가 최소가 될 것이다.

R 값을 고정하고 나면, 감염된 소들 중에서 서로 거리가 R 이내에 있는 소들은 하나의 그룹으로 묶어준다. 

최종적으로 구하는 답은 그룹의 개수이다. 

 

[소스 코드]

 

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
using namespace std;
const int MAX = 2e9;

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int N; cin >> N;
	vector<pii> v;
	for (int i = 1; i <= N; i++) {
		int x, s; cin >> x >> s;
		v.push_back({ x, s });
	}
	sort(all(v));
	int dis = MAX;
	for (int i = 0; i < sz(v); i++) {
		if (v[i].second == 0) {
			if (i > 0 && v[i - 1].second == 1) dis = min(dis, v[i].first - v[i - 1].first);
			if (i < sz(v) - 1 && v[i + 1].second == 1) dis = min(dis, v[i + 1].first - v[i].first);
		}
	}
	int ans = 0;
	int last = -1;
	for (int i = 0; i < sz(v); i++) {
		if (v[i].second == 1) {
			if (last == -1) {
				ans++;
			}
			else if (v[i].first - last >= dis) {
				ans++;
			}
			last = v[i].first;
		}
	}
	cout << ans;
}

  

 

3. [BOJ 18882] Cowntact Tracing  Silver III

 

 

[문제 설명]

 

주어진 소 중에서 질병에 걸린 소가 일부 존재한다. 제일 처음 질병에 걸린 소가 존재하고, 질병은 감염된 소와 서로 상호작용을 하게 되면 감염되며, 감염된 후 K번 다른 소들과 상호작용하면 더 이상 다른 소를 감염시키지 않는다. 

한번 질병에 걸리면 걸린 상태가 그대로 유지될 때, 최종적으로 소들의 감염여부가 주어진다.

그리고 상호작용을 한 소 번호와 시간 기록들이 주어질 때, 제일 처음 질병에 걸린 소로 가능한 소의 수와 K의 최댓값, 최솟값을 구해야한다. 

 

[풀이]

 

우선, N과 T의 제한이 작아서 모든 경우를 다 고려하는 완전 탐색(Brute-force)이 가능하다. 

첫번째로 처음 질병에 걸린 소를 정해놓고 시작하면 N가지의 경우가 나온다. 

그리고 가능한 K의 값은 0~T이므로 K값 또한 고정시키면 T가지의 경우가 나오고, 

N과 K를 고정시킨 후 모든 t에 대해서 소들의 상호작용을 확인해야하므로 최종적으로 $O(NT^2)$의 시간복잡도를 갖는다.

 

[소스 코드]

 

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

pii A[251];
int ori[101];
int can[101];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int N, T; cin >> N >> T;
	string s; cin >> s;
	int mxt = 0;
	for (int i = 0; i < N; i++) ori[i + 1] = s[i] - '0';
	for (int i = 1; i <= T; i++) {
		int t, a, b; cin >> t >> a >> b;
		A[t] = { a, b };
		mxt = max(mxt, t);
	}
	int x, y, z;
	x = 0;
	y = 10000;
	z = 0;
	for (int i = 1; i <= N; i++) {
		if (ori[i] == 0) continue;
		for (int k = 0; k <= T; k++) {
			vector<int> cnt(N + 1), cow(N + 1);
			cow[i] = 1;
			for (int j = 1; j <=mxt; j++) {
				int u = A[j].first;
				int v = A[j].second;
				if ((cow[u] == 1 || cow[v] == 1)) {
					if (cow[u] == 1) cnt[u]++;
					if (cow[v] == 1) cnt[v]++;
					if ((cow[u] == 1 && cnt[u] <= k) || (cow[v] == 1 && cnt[v] <= k)) {
						cow[u] = cow[v] = 1;
					}
				}
			}
			bool chk = true;
			for (int j = 1; j <= N; j++) if (cow[j] != ori[j]) chk = false;
			if (chk) {
				z = max(z, k);
				y = min(y, k);
				can[i] = 1;
			}
		}
	}
	for (int i = 1; i <= N; i++) if (can[i] == 1) x++;
	cout << x << ' ' << y << ' ';
	if (z == 250) cout << "Infinity";
	else cout << z;
}

 

PC로 보시는 것을 권장합니다. 

피드백은 언제나 환영입니다. 댓글로 달아주세요 ^-^

 

반응형