A - Cut
문제 요약
길이 n인 수열에서 마지막 k개 원소를 앞으로 이동시킨 결과를 출력한다.
핵심 아이디어
배열을 회전시키는 기초적인 구현 문제이다. n-k 인덱스부터 끝까지의 원소를 먼저 출력한 뒤, 나머지 원소를 순서대로 출력하면 된다.
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> arr(n);
for (int &x : arr) cin >> x;
// 뒷부분 먼저 출력
for (int i = n - k; i < n; i++) {
cout << arr[i] << " ";
}
// 앞부분 출력
for (int i = 0; i < n - k; i++) {
cout << arr[i] << " ";
}
return 0;
}
B - Decrease 2 max elements
문제 요약
양의 정수들로 이루어진 배열에서, 매 단계 가장 큰 두 값을 각각 1씩 감소시킨다. 더 이상 감소시킬 수 없을 때(두 번째로 큰 값이 0 이하)까지 번 연산을 수행할 수 있는지 구한다.
핵심 아이디어
직접 시뮬레이션도 가능하지만, 수학적 관찰로 O(n) 풀이가 가능하다. 매 2회 연산에서 총 2만큼 감소시키므로, 전체 합의 절반만큼은 확실히 연산 가능하다. 하지만 가장 값이 과도하게 크면 다른 값들이 먼저 소진되어 연산이 제한되므로, min(총합/2, 총합-최대값)이 답이 된다.
시뮬레이션 풀이
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
int operations = 0;
while (true) {
sort(a.begin(), a.end(), greater<int>());
if (a[1] <= 0) break;
a[0]--;
a[1]--;
operations++;
}
cout << operations;
}
수학적 풀이
void solve() {
int n;
cin >> n;
long long total = 0;
int mx = 0;
for (int i = 0; i < n; i++) {
int x; cin >> x;
total += x;
mx = max(mx, x);
}
cout << min(total / 2, total - mx);
}
C - Triple Attack
문제 요약
n명의 적이 있고, i번째 적의 체력은 h[i]이다. 시간 t=0부터 시작하여 매 턴 t를 1 증가시킨다. t가 3의 배수이면 3의 데미지를, 아니면 1의 데미지를 입힌다. 모든 적의 체력을 0 이하로 만들기 위한 최소 턴 수를 구한다.
핵심 아이디어
3턴을 주기로 보았을 때 총 5의 데미지를 입힌다(1+1+3). 각 적에 대해 h[i]/5만큼의 주기를 한 번에 계산하고, 나머지 체력은 직접 시뮬레이션한다. 남은 체력은 최대 4이므로 2턴 이내로 해결된다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> hp(n);
for (ll &x : hp) cin >> x;
ll turns = 0;
for (ll &h : hp) {
// 3턴 주기로 5데미지
turns += (h / 5) * 3;
h %= 5;
// 남은 체력 처리
while (h > 0) {
turns++;
h -= (turns % 3 == 0 ? 3 : 1);
}
}
cout << turns;
return 0;
}
D - Minimum Steiner Tree
문제 요약
n개의 정점으로 이루어진 트리에서 k개의 필수 정점이 주어진다. 불필요한 정점과 간선을 제거하되 모든 필수 정점이 연결되도록 남겨둘 때, 최소 몇 개의 정점을 남겨야 하는가?
핵심 아이디어
Steiner Tree의 특수한 경우(트리 구조)로, DFS를 통해 해결한다. 임의의 필수 정점에서 시작하여, 각 서브트리에 필수 정점이 포함되어 있는지 확인한다. 자식 서브트리에 필수 정점이 하나라도 있거나, 현재 정점 자체가 필수 정점이면 해당 정점은 반드시 남겨야 한다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
bool required[MAXN];
bool visited[MAXN];
int dfs(int u) {
visited[u] = true;
int keep = 0; // 이 서브트리에 남겨야 할 정점 수
for (int v : adj[u]) {
if (!visited[v]) {
keep += dfs(v);
}
}
// 자식 중 필수 정점이 있거나, 자신이 필수 정점이면 유지
if (keep > 0 || required[u]) {
keep++;
}
return keep;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int start = -1;
for (int i = 0; i < k; i++) {
int x; cin >> x;
required[x] = true;
start = x;
}
cout << dfs(start);
return 0;
}
F - Dividing Game
문제 요약
n개의 정수가 주어지고, 두 플레이어가 번갈아가며 하나의 수를 선택하여 자신의 진약수(1과 자신을 제외한 약수)로 바꾼다. 더 이상 움직일 수 없는 플레이어가 패배한다. 양측 모두 최적으로 플레이할 때 승자를 판정한다.
핵심 아이디어
각 수를 독립적인 게임으로 보고 Sprague-Grundy 정리를 적용한다. sg(x)는 x의 모든 진약수 d에 대한 sg(d)들의 mex(minimum excluded value)이다. 전체 게임의 Grundy 수는 각 수의 Grundy 수의 XOR이며, 0이면 후공(Bruno) 승, 아니면 선공(Anna) 승이다.
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1e6 + 5;
int memo[MAXV];
bool calculated[MAXV];
int grundy(int x) {
if (calculated[x]) return memo[x];
unordered_set<int> reachable;
for (int d = 2; d * d <= x; d++) {
if (x % d == 0) {
// d는 진약수
if (d != x) reachable.insert(grundy(d));
int other = x / d;
if (other != x && other != d) reachable.insert(grundy(other));
}
}
// 1은 항상 진약수 (x > 1일 때)
if (x > 1) reachable.insert(grundy(1));
// mex 계산
int g = 0;
while (reachable.count(g)) g++;
calculated[x] = true;
return memo[x] = g;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int totalXor = 0;
for (int i = 0; i < n; i++) {
int x; cin >> x;
totalXor ^= grundy(x);
}
cout << (totalXor ? "Anna" : "Bruno");
return 0;
}
참고: grundy(1) = 0이며, 소수 p에 대해 grundy(p) = 1이다.