A. Contest Start (수학)
이 문제는 패턴을 분석하는 문제입니다. 참가자들의 시작 시간이 일정한 간격으로 배치될 때, 각 참가자가 기다려야 하는 평균 시간을 구해야 합니다. 먼저, 한 참가자가 끝날 때까지 기다리는 다른 참가자의 수를 생각해봅시다. 만약 한 참가자의 경기 시간이 \(t\)이고, 다음 참가자와의 시작 시간 차이가 \(x\)라면, 한 참가자가 경기하는 동안 \(t/x\)명의 참가자가 추가로 시작하게 됩니다. 이때, 전체 \(n\)명의 참가자 중에서 앞쪽 \(t/x\)명은 모두 같은 수의 대기자를 가지게 되고, 나머지 뒷쪽 참가자들은 점점 줄어드는 대기자 수를 가지게 됩니다. 따라서 전체 대기 시간의 합은 두 부분으로 나누어 계산할 수 있습니다. 앞부분은 \(num = t/x\)라고 할 때, 각 참가자가 \(num\)명을 기다리게 되고, 뒷부분은 등차수열을 이룹니다. \(num\)이 \(n\)보다 크거나 같으면 모든 참가자가 동일한 대기자 수를 가지므로 \(n(n-1)/2\)를 출력하고, 그렇지 않으면 앞부분의 합 \((num+1) \times num / 2\)와 뒷부분 \((n - num - 1) \times num\)을 더해서 출력합니다. 데이터 타입은 long long을 사용해야 합니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
long long n, x, t;
cin >> n >> x >> t;
long long cnt = t / x;
if (cnt >= n) {
cout << n * (n - 1) / 2 << "\n";
} else {
cout << cnt * (cnt + 1) / 2 + (n - cnt - 1) * cnt << "\n";
}
}
return 0;
}
B. Love Song (누적 합)
문자열의 각 문자를 알파벳 순서에 해당하는 숫자로 변환한 후, 주어진 구간 \([l, r]\)에 대해 각 문자가 나타난 횟수에 해당 숫자를 곱한 합을 구하는 문제입니다. 이것은 전형적인 누적 합(prefix sum) 문제입니다. 각 알파벳에 대해 누적 합 배열을 만들면, 구간 쿼리를 \(O(1)\)에 처리할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, q, pref[MAXN][26];
string s;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q >> s;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 26; j++) {
pref[i][j] = pref[i-1][j];
}
pref[i][s[i-1] - 'a']++;
}
while (q--) {
int l, r, ans = 0;
cin >> l >> r;
for (int j = 0; j < 26; j++) {
ans += (pref[r][j] - pref[l-1][j]) * (j + 1);
}
cout << ans << "\n";
}
return 0;
}
C. Stable Groups (그리디)
주어진 수열을 정렬한 후, 인접한 원소 간의 차이가 \(x\) 이하인 것들을 하나의 그룹으로 묶는 것이 기본입니다. 여기서 \(k\)개의 원소를 추가하여 그룹을 더 합칠 수 있습니다. 이 문제는 그리디하게 해결할 수 있습니다. 먼저 정렬된 배열에서 인접한 원소 간의 차이가 \(x\)보다 큰 경우, 그 간격을 기록합니다. 각 간격을 메우기 위해 필요한 추가 원소의 개수는 \(\lceil \frac{cha}{x} \rceil - 1\)입니다. 여기서 \(cha\)는 두 원소의 차이입니다. 이제 모든 간격을 우선순위 큐에 넣고, 필요한 원소 수가 적은 것부터 처리합니다. 만약 \(k\)가 그 간격을 메우기에 충분하다면 그룹을 하나 줄이고, \(k\)를 차감합니다. 그렇지 않으면 종료합니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
int n, groups = 1;
ll k, x, arr[MAXN];
priority_queue<ll, vector<ll>, greater<ll>> gaps;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> x;
for (int i = 0; i < n; i++) cin >> arr[i];
sort(arr, arr + n);
for (int i = 1; i < n; i++) {
if (arr[i] - arr[i-1] > x) {
gaps.push(arr[i] - arr[i-1]);
groups++;
}
}
while (!gaps.empty()) {
ll dist = gaps.top();
gaps.pop();
ll need = dist / x;
if (dist % x == 0) need--;
if (k < need) break;
k -= need;
groups--;
}
cout << groups << "\n";
return 0;
}
D. PriceFixed (그리디, 시뮬레이션)
이 문제는 다음과 같은 두 가지 중요한 성질을 이용합니다: - 성질 1: 가격이 1인 품목이 있고 아직 구매해야 할 수량이 남았다면, 먼저 구매합니다. - 성질 2: 이미 필요한 수량을 만족한 품목을 추가로 구매하여 다른 품목의 가격을 1로 만드는 것은 이득이 되지 않습니다. 성질 2는 수학적으로 증명됩니다. 만약 어떤 품목의 남은 필요 수량이 \(j\)개이고, 이 품목의 가격을 1로 만들기 위해 추가로 구매해야 하는 수량이 \(k\)개라면: - \(k \le j\)인 경우: \(k + j\)와 \(2k + (j - k) = k + j\)로 동일합니다. - \(k > j\)인 경우: \(k + j\)보다 \(2j\)가 더 작으므로 직접 구매가 유리합니다. 따라서, 품목들을 \(b_i\) 기준으로 오름차순 정렬한 후, 시뮬레이션을 통해 최소 비용을 계산합니다. 현재까지 구매한 수량을 추적하면서, 각 품목의 할인 조건을 만족할 때까지 필요한 만큼 구매하고, 이후 남은 수량을 처리합니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
struct Item {
ll a, b;
} items[MAXN];
int n;
bool cmp(Item &x, Item &y) {
return x.b < y.b;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
ll totalNeed = 0;
for (int i = 0; i < n; i++) {
cin >> items[i].a >> items[i].b;
totalNeed += items[i].a;
}
sort(items, items + n, cmp);
ll bought = 0, ans = 0;
int idx = 0;
while (bought < totalNeed) {
if (idx >= n) break;
ll canBuy = min(items[idx].b - bought, totalNeed - bought);
if (canBuy > 0) {
bought += canBuy;
ans += canBuy;
}
ll nowBuy = min(totalNeed - bought, items[idx].a);
bought += nowBuy;
ans += nowBuy;
idx++;
}
cout << 2 * totalNeed - ans << "\n";
return 0;
}