A - UPC 조합
문제 개요
입력 문자열의 첫 번째 글자 뒤에 "UPC"를 붙여 출력한다.
핵심 아이디어
문자열 인덱싱을 활용한 단순 구현.
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string str;
cin >> str;
cout << str.front() << "UPC" << '\n';
return 0;
}B - 무거운 뱀
문제 개요
n마리 뱀의 길이와 두께이 주어진다. 각 뱀의 무게는 길이×두께. 매일 모든 뱀의 길이가 1씩 증가할 때, D일 동안 매일 가장 무거운 뱀의 무게를 구한다.
핵심 아이디어
매일 길이를 증가시키고 전체 정렬하여 최댓값을 추출. O(D × n log n)으로 제약 내 해결 가능.
구현
#include <bits/stdc++.h>
using namespace std;
struct Snake {
long long thick, len;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, days;
cin >> n >> days;
vector<Snake> snakes(n);
for (auto& s : snakes) {
cin >> s.thick >> s.len;
}
auto cmp = [](const Snake& x, const Snake& y) {
return x.thick * x.len > y.thick * y.len;
};
for (int d = 1; d <= days; ++d) {
for (auto& s : snakes) {
s.len++;
}
sort(snakes.begin(), snakes.end(), cmp);
cout << snakes[0].thick * snakes[0].len << '\n';
}
return 0;
}C - 다양한 거울떡
문제 개요
오름차순으로 주어지는 n개의 떡 크기에서, 작은 떡을 큰 떡 위에 올릴 수 있다. 단, 아래 떡의 크기가 위 떡의 2배 이상이어야 한다. 만들 수 있는 떡 조합의 수를 구한다.
핵심 아이디어
각 떡을 아래쪽으로 사용할 때, 위에 올릴 수 있는 떡의 개수를 lower_bound로 빠르게 계산. 전체 복잡도 O(n log n).
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> rice(n);
for (auto& x : rice) cin >> x;
long long total = 0;
for (int i = 0; i < n; ++i) {
auto it = lower_bound(rice.begin(), rice.end(), rice[i] * 2);
if (it != rice.end()) {
total += rice.end() - it;
}
}
cout << total << '\n';
return 0;
}D - 성인식
문제 개요
n명의 미성년자가 있고, i번째 사람은 ai개의 보석을 가지고 i년째에 성인이 된다. 성인이 될 때, 기존 성인들이 보석이 있다면 각각 1개쵸 나눠준다. n년 후 각자의 보석 개수를 출력한다.
핵심 아이디어
구간 업데이트와 점 쿼리가 필요하므로 세그먼트 트리 또는 펜윅 트리 활용. Lazy propagation으로 구간 덧셈 최적화.
구현
#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
vector<long long> bit;
int n;
Fenwick(int sz) : n(sz), bit(sz + 1) {}
void add(int idx, long long val) {
for (; idx <= n; idx += idx & -idx) bit[idx] += val;
}
void rangeAdd(int l, int r, long long val) {
add(l, val);
add(r + 1, -val);
}
long long query(int idx) {
long long res = 0;
for (; idx > 0; idx -= idx & -idx) res += bit[idx];
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> gems(n + 1);
for (int i = 1; i <= n; ++i) cin >> gems[i];
Fenwick fw(n);
for (int i = 1; i <= n; ++i) {
long long received = fw.query(i);
long long available = gems[i] + received;
long long give = min(available, (long long)(n - i));
if (give > 0) {
fw.rangeAdd(i + 1, min(i + (int)give, n), 1);
gems[i] = available - give;
} else {
gems[i] = available;
}
}
for (int i = 1; i <= n; ++i) {
cout << gems[i] << " \n"[i == n];
}
return 0;
}E - 동시 거울떡 최대화
문제 개요
C번과 유사하나, 동시에 만들 수 있는 거울떡 쌍의 최대 개수를 구한다.
핵심 아이디어
매개변수 탐색(Parametric Search). x개의 쌍을 만들 수 있는지 판정하는 check 함수를 설계. 작은 떡들끼리, 큰 떡들끼리 매칭하는 그리edy한 전략이 최적.
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> mochi(n);
for (auto& x : mochi) cin >> x;
auto feasible = [&](int pairs) -> bool {
for (int i = 0; i < pairs; ++i) {
if (mochi[i] * 2 > mochi[n - pairs + i]) {
return false;
}
}
return true;
};
int low = 0, high = n / 2, best = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (feasible(mid)) {
best = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << best << '\n';
return 0;
}문제 출처: AtCoder Beginner Contest 388