봇은 항상 칠할 수 있는 가장 왼쪽 칸만을 골라 칠하므로 봇의 차례에는 앞으로 칠할 수 있는 칸의 수가 1 또는 2 감소할 수 있다.
존은 칠할 수 있는 곳을 적절하게 골라 칠할 수 있으므로 존의 차례에는 앞으로 칠할 수 있는 칸의 수가 1 또는 2 또는 3 감소할 수 있다.
따라서 만약 칸이 5개 이하로 남을 때까지 봇의 차례에는 앞으로 칠할 수 있는 칸의 수가 항상 2 감소하고 존의 차례에는 항상 3 감소하게끔 두 플레이어가 행동할 수 있다면 이 때 봇이 얻을 수 있는 점수가 최소화될 것이다. 이러한 전략은 항상 존재하는데, 이 방법을 찾는 것은 어렵지 않으므로 이를 찾아보는 것은 읽는이들에게 남긴다.
아래는 제출한 소스코드이다.
#include <iostream>
using namespace std;
int T, N;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
for (int t = 1; t <= T; t++) {
cin >> N;
cout << "Case #" << t << ": " << (N - 1) / 5 + 1 << '\n';
}
}
이 문제는 두 작은 문제를 해결해야 한다. 하나는 'H', 'Y', 'U'가 아닌 모든 문자를 지우는 데에 필요한 에너지의 최솟값을 구하는 것이고 다른 하나는 만들 수 있는 "HYU"의 개수를 구하는 것이다. 두 번째 문제의 경우 'H', 'Y', 'U' 중 가장 적은 문자의 개수만큼은 "HYU"를 항상 만들 수 있지만 그보다 많은 개수는 항상 만들 수 없다는 점을 관찰해 쉽게 해결할 수 있다. 아래에서는 첫 번째 문제의 해결 방법을 살펴보자.
지워야 하는 두 문자 사이에 'H', 'Y', 'U'가 끼어있으면 해당 두 문자를 드래그로 같이 선택해 지울 수 없다는 점을 확인하자. 따라서 주어지는 문자열을 'H', 'Y', 'U'을 기준으로 잘라 얻을 수 있는 각 부분문자열을 지우는 에너지의 합을 구하는 것으로 문제의 답을 구할 수 있다.
모든 문자가 지워야 할 문자일 때 드래그를 두 번 이상 하고 지우는 것은 모든 문자를 한 번에 드래그하고 지우는 것보다 항상 많은 에너지가 든다는 점을 관찰하자. 따라서 최소 에너지를 구할 때 드래그는 많아야 한 번만 할 수 있다고 가정해도 문제의 답을 충분히 구할 수 있다. 드래그를 하는 경우와 하지 않는 경우의 에너지 사용량을 각각 구해 문제를 해결하자.
두 작은 문제 모두 답이 0인 경우 0이 아닌 문제에 주어진 문자열을 출력해야 하는 점을 유의하자.
아래는 제출한 소스코드이다.
#include <iostream>
#include <string>
using namespace std;
int N, D, M;
string s;
int cnt[128], combo;
int ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> s >> D >> M;
for (auto &l : s) {
if (l == 'H') {
cnt['H']++;
ans += min(M + D, combo * D);
combo = 0;
}
else if (l == 'Y') {
cnt['Y']++;
ans += min(M + D, combo * D);
combo = 0;
}
else if (l == 'U') {
cnt['U']++;
ans += min(M + D, combo * D);
combo = 0;
}
else combo++;
}
ans += min(M + D, combo * D);
if (ans) cout << ans << '\n';
else cout << "Nalmeok\n";
ans = min(cnt['H'], min(cnt['Y'], cnt['U']));
if (ans) cout << ans;
else cout << "I love HanYang University";
}
먼저 매 순간 두 개의 다리가 지워지므로 다리의 개수 \(M\)이 짝수이면 어떤 다리도 마지막 남은 하나의 다리가 될 수 없다. 다음 문단부터는 \(M\)이 홀수라 가정하자.
어떤 다리가 마지막으로 남을 수 있다는 것과 해당 다리를 제외한 다리들로 구성된 그래프는 주어진 조건을 따라 다리를 모두 없앨 수 있다는 것은 동치임을 관찰하자. 이 때, 다음이 성립함을 관찰하면 이 문제를 푸는 것은 "없앴을 때 그래프를 다리의 개수가 각각 홀수인 두 connected component로 나눠버리는 다리"를 찾는 것과 같음을 쉽게 확인할 수 있다.
짝수 개의 다리를 갖는 connected component는 주어진 조건을 따라 모든 다리를 항상 없앨 수 있다.
위 관찰은 다음과 같은 두 명제를 보이는 것으로 귀납적으로 증명할 수 있다. 그 증명은 어렵지 않으므로 간단한 스케치만 남겨 둔다.
(1) 주어진 connected component가 홀수 개의 에지로 이루어져 있다면 임의의 섬에서 하나의 에지를 지워 짝수 개의 에지로 이루어진 connected component(여러 개일 수 있음)를 얻을 수 있다.
(1)의 추가 설명: 고른 섬이 둘 이상의 섬으로 이루어진 biconnected component에 포함된다면 이면 해당 component에 포함되는 에지를 하나 지우면 되고, 그렇지 않다면 전체 에지가 홀수 개임을 이용해 끊었을 때 두 connected component의 각 에지의 개수가 모두 짝수가 되게 하는 에지가 항상 존재하게 됨을 보이자.
(2) 주어진 connected component가 짝수 개의 에지로 이루어져 있다면 임의의 섬에서 하나의 에지를 지워 홀수 개의 에지로 이루어진 connected component(와 덤으로 나올 수 있는 짝수 개의 에지로 이루어진 connected component)를 얻을 수 있다.
따라서 마지막으로 남을 수 있는 다리는 주어진 그래프에서 "끊었을 때 크기가 홀수인 두 component로 그래프를 쪼개는 다리"를 제외한 모든 다리들이다. 주어진 그래프의 bridge들을 한 번씩 확인해 문제를 해결하자. 해당 bridge를 끊었을 때 나누어지는 두 component가 각각 포함하는 에지의 수는 Block-cut Tree(각 biconnected component를 노드로 갖는 Tree) 위에서의 Tree DP와 같은 접근으로 빠르게 계산할 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int N, M;
map<pair<int, int>, int> mp;
vector<int> G[300001];
bool ans[300001];
int dfidx, dfi[300001];
pair<int, int> dfs(int cur, int par) { // 리턴값: 만난 최소 dfi, 에지 수
dfidx++;
int ret = dfi[cur] = dfidx, cnt = 0;
if (cur == par) cnt++;
for (auto &nxt:G[cur]) {
if (nxt == par) continue;
if (dfi[nxt]) ret = min(ret, dfi[nxt]);
else {
auto tmp = dfs(nxt, cur);
ret = min(ret, tmp.first);
cnt += tmp.second;
}
}
cnt += G[cur].size() - 1;
if (ret == dfi[cur] && ((cnt / 2) & 1) && par) {
ans[mp[make_pair(min(cur, par), max(cur, par))]] = 1;
}
cnt++;
return make_pair(ret, cnt);
}
int anscnt;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
if (M % 2 == 0) {
cout << 0;
return 0;
}
for (int i = 1; i <= M; i++) {
int x, y; cin >> x >> y;
G[x].emplace_back(y);
G[y].emplace_back(x);
mp.insert(make_pair(make_pair(min(x, y), max(x, y)), i));
}
dfs(1, 0);
for (int i = 1; i <= M; i++) {
if (ans[i]) continue;
anscnt++;
}
cout << anscnt << '\n';
for (int i = 1; i <= M; i++) {
if (ans[i]) continue;
cout << i << ' ';
}
}
각 테스트케이스 별로 그래프에서 특정 에지가 MST(최소 신장 트리)에 포함될 수 있는지 판별할 것을 요구하는 문제이다.
주어지는 그래프의 MST는 유일하지 않으므로 MST를 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm)등으로 아무거나 하나 구해 대조하는 것만으로는 문제를 해결할 수 없다. 모든 에지의 가중치가 같은 완전그래프를 생각해 보면 이는 간단하게 이해할 수 있을 것이다.
이 문제를 해결하는 방법은 여러 가지가 있다. 이 글에서는 그 중 두 가지를 간략하게 소개한다.
1. 크루스칼 알고리즘(Kruskal's Algorithm)의 변형
크루스칼 알고리즘에서 각 에지를 살펴 MST에 추가할 수 있다는 것을 확인 후 해당 에지를 바로 MST에 추가하는 대신 같은 가중치의 에지들을 묶어 각각 MST에 추가할 수 있는지 따로 확인한 다음 그 에지 중 추가할 수 있는 에지들을 MST에 추가하는 방법이다.
2. 주어진 그래프의 MST를 구성하는 비용과 주어진 에지를 우선적으로 먼저 집어넣고 나머지 노드를 최소비용으로 합쳤을 때의 비용을 구한 다음 두 값이 같은지 대조
글쓴이는 1번 방법을 구현하여 문제를 해결했다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int T, N, M, P, Q;
int arr[10001];
int findf(int x) {
if (arr[x] == x) return x;
return arr[x] = findf(arr[x]);
}
vector<pair<int, pair<int, int>>> E;
void solve() {
E.clear();
cin >> N >> M >> P >> Q;
if (P > Q) swap(P, Q);
auto PP = make_pair(P, Q);
while (M--) {
int x, y, w; cin >> x >> y >> w;
if (x > y) swap(x, y);
E.emplace_back(make_pair(w, make_pair(x, y)));
}
sort(E.begin(), E.end());
for (int i = 1; i <= N; i++) arr[i] = i;
int old = -1; vector<pair<int, int>> tmp;
for (auto &p : E) {
if (old < p.first) {
for (auto &pp : tmp) {
int x = findf(pp.first), y = findf(pp.second);
if (x != y) arr[y] = x;
}
old = p.first;
tmp.clear();
}
int x = findf(p.second.first), y = findf(p.second.second);
if (x != y) {
if (p.second == PP) {
cout << "YES\n";
return;
}
tmp.emplace_back(p.second);
}
}
cout << "NO\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> T;
while (T--) solve();
}
주어진 배열에 등장하는 수 \(x\)에 대하여 해당 수를 양 끝으로 갖는 "순서쌍의 최대 합"은 배열에 처음 등장한 \(x\)의 위치부터 마지막으로 등장한 \(x\)의 위치까지의 구간합과 같음을 관찰하자.
따라서 주어진 배열에 등장하는 각 원소에 대하여 처음 등장한 위치와 마지막으로 등장한 위치를 map 등을 이용해 관리하고, 구간합을 빠르게 구하기 위해 prefix sum을 이용하는 것으로 문제를 해결할 수 있다. 시간복잡도는 map을 사용하는 데에 따라 발생하는 \(O(N\lg N)\)이다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
int N;
ll arr[200001];
map<int, int> L, R;
ll ans, cnt;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
int x; cin >> x;
arr[i] = arr[i - 1] + x;
if (L.count(x)) {
L[x] = min(L[x], i), R[x] = max(R[x], i);
}
else {
L.insert(make_pair(x, i)), R.insert(make_pair(x, i));
}
}
for (auto& p : L) {
ll val = arr[R[p.first]] - arr[p.second - 1];
if (val > ans) ans = val, cnt = 1;
else if (val == ans) cnt++;
}
cout << ans << ' ' << cnt;
}
주어진 띠의 인접한 두 수가 정렬된 상태에서 서로 인접하지 않는다면 이 두 수 사이는 항상 분리해야 함을 관찰하자. 절단하지 않으면 어떤 방법을 사용해도 이 두 수 사이에 다른 수가 삽입될 수 없기 때문이다. 따라서 띠의 인접한 두 수들 중 정렬된 상태에서 인접하지 않은 두 수 사이는 모두 분리해야 함을 알 수 있다.
한편, 위와 같이만 분리해도 주어진 띠를 올바르게 정렬된 띠로 항상 만들 수 있음을 관찰하자. 각 나눠진 조각은 정렬된 상태의 일부분 또는 그 역순 뿐이기 때문이다.
따라서 위의 분리해야 하는 점의 수를 세는 것으로 문제를 해결할 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool comp(pair<int, int>& p1, pair<int, int>& p2) {
return p1.second < p2.second;
}
int N;
pair<int, int> arr[200000];
int ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) arr[i].first = i, cin >> arr[i].second;
sort(arr, arr + N, comp);
for (int i = 0; i < N; i++) arr[i].second = i;
sort(arr, arr + N);
for (int i = 0; i + 1 < N; i++) {
if (abs(arr[i].second - arr[i + 1].second) > 1) ans++;
}
cout << ans;
}