알파카컵 1회: B - 알파카 농장
1. 문제 요약
\(N\)일 동안 매일 \(A_i\)개의 풀이 주어지지만, 알파카는 위장의 한계치 \(K\)를 초과하는 풀은 모두 뱉어내므로 \(i\)번째 날 실제로 먹는 양은 \(\min(A_i, K)\)입니다. 따라서 \(N\)일 동안 알파카가 먹는 총 풀의 양은 다음과 같습니다.
$$ \text{eaten}(K) = \sum_{i=1}^{N} \min(A_i, K) $$
우리는 이 총량이 \(L\) 이상이 되도록 하는 최소 \(K\)를 찾고, 그때 뱉어낸 풀의 총량 \(\sum_{i=1}^{N} \max(0, A_i - K)\)을 구해야 합니다. \(K\)가 커질수록 각 \(\min(A_i, K)\)는 줄어들지 않으므로 \(\text{eaten}(K)\)는 \(K\)에 대해 단조 증가한다는 것이 풀이의 핵심입니다.
2. [서브태스크 1]: \(A_1 + \cdots + A_N = L\)
모든 풀의 합이 정확히 \(L\)인 특수한 경우입니다. 알파카가 단 한 개의 풀도 뱉어내지 않고 전부 먹어야만 \(L\)개를 채울 수 있습니다.
-
풀이: 하나라도 풀을 뱉어내면 총합이 \(L\) 미만이 되어 조건을 만족할 수 없습니다. 따라서 모든 날 \(A_i \le K\)여야 하며, 이를 만족하는 최소 \(K\)는 \(\max(A_i)\)입니다. 이때 뱉어낸 양은 항상 \(0\)입니다.
-
시간 복잡도: 최댓값을 한 번 훑는 \(O(N)\)입니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, L;
ll a[100001];
int main() {
fastio
cin >> n >> L;
ll mx = 0;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
}
cout << mx << endl;
cout << 0 << endl;
return 0;
}
3. [서브태스크 2]: \(1 \le N \le 20\)
\(N\)이 최대 20으로 매우 작은 경우입니다. 정답 \(K\)를 찾기 위해 자유롭게 후보들을 직접 확인해 볼 여유가 있습니다.
-
풀이: \(\text{eaten}(K)\)는 두 인접한 \(A_i\) 값 사이의 구간에서 \(K\)에 대한 일차함수(선형)로 증가합니다. \(A_i\) 값들과 \(0\)을 정렬해 만든 각 구간 \((\text{lo}, \text{hi}]\)를 작은 것부터 살펴보며, 그 구간이 \(K\)만큼 늘 때 추가로 먹는 양의 기울기(\(\text{lo}\)보다 큰 \(A_i\)의 개수)를 이용해 \(\text{eaten}(K) \ge L\)이 되는 최소 \(K\)를 직접 계산합니다.
-
시간 복잡도: 후보 정렬에 \(O(N \log N)\), 각 구간마다 \(\text{eaten}\)과 기울기를 \(O(N)\)에 다시 세므로 최악의 경우 \(O(N^2)\)이지만, \(N \le 20\)에서는 순식간에 끝납니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, L;
ll a[100001];
ll eaten(ll k) {
ll sum = 0;
for (ll i = 1; i <= n; i++) sum += min(a[i], k);
return sum;
}
int main() {
fastio
cin >> n >> L;
ll mx = 0;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
}
// 후보 K들을 정렬해 구간(band)별로 직접 확인한다.
vector<ll> cand;
cand.push_back(0);
for (ll i = 1; i <= n; i++) cand.push_back(a[i]);
sort(cand.begin(), cand.end());
cand.erase(unique(cand.begin(), cand.end()), cand.end());
ll ansK = mx;
for (ll t = 0; t + 1 < (ll)cand.size(); t++) {
ll lo = cand[t], hi = cand[t + 1];
// (lo, hi] 구간에서 K가 1 늘 때 더 먹는 양 = (A_i > lo 인 개수)
ll cnt = 0;
for (ll i = 1; i <= n; i++) if (a[i] > lo) cnt++;
ll base = eaten(lo);
if (base + cnt * (hi - lo) >= L) {
ll need = L - base;
ll step = (need + cnt - 1) / cnt; // 올림
ansK = lo + step;
break;
}
}
ll spat = 0;
for (ll i = 1; i <= n; i++) spat += max(0LL, a[i] - ansK);
cout << ansK << endl;
cout << spat << endl;
return 0;
}
4. [서브태스크 3]: \(1 \le N \le 500\)
\(N\)이 500까지 커집니다. 서브태스크 2의 구간 직접 계산법도 통과하지만, 여기서부터는 \(\text{eaten}(K)\)의 단조성을 활용한 이진 탐색이라는 정형화된 풀이를 사용하는 것이 깔끔합니다.
-
풀이: \(\text{eaten}(K)\)가 \(K\)에 대해 단조 증가하므로, \(\text{eaten}(K) \ge L\)을 만족하는 \(K\)의 경계를 이진 탐색으로 찾을 수 있습니다. 탐색 범위는 \(K \in [1, \max(A_i)]\)로 잡습니다(\(K\)가 \(\max(A_i)\) 이상이면 모든 풀을 먹으므로 더 키울 이유가 없습니다). 각 후보 \(K\)에 대해 \(\text{eaten}(K)\)를 \(O(N)\)에 직접 계산해 조건을 판정합니다. 최소 \(K\)를 찾은 뒤 뱉어낸 양 \(\sum \max(0, A_i - K)\)을 한 번 더 훑어 출력합니다.
-
시간 복잡도: \(\text{eaten}\) 판정이 \(O(N)\), 이진 탐색이 \(O(\log(\max A))\)회 반복되어 \(O(N \log(\max A))\)입니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, L;
ll a[100001];
ll eaten(ll k) {
ll sum = 0;
for (ll i = 1; i <= n; i++) sum += min(a[i], k);
return sum;
}
int main() {
fastio
cin >> n >> L;
ll mx = 0;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
}
ll lo = 1, hi = mx, ansK = mx;
while (lo <= hi) {
ll mid = (lo + hi) / 2;
if (eaten(mid) >= L) {
ansK = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
ll spat = 0;
for (ll i = 1; i <= n; i++) spat += max(0LL, a[i] - ansK);
cout << ansK << endl;
cout << spat << endl;
return 0;
}
5. [서브태스크 4]: \(1 \le N \le 2000\)
\(N\)이 2000까지 늘어난 경우입니다. 서브태스크 3에서 사용한 이진 탐색은 \(N\)에 대해 한 번만 선형으로 비례하므로, 별도의 수정 없이 그대로 통과합니다.
-
풀이: 서브태스크 3과 동일한 이진 탐색을 사용합니다. 여기서 반드시 주의할 점은 자료형 오버플로입니다. \(\text{eaten}(K)\)의 누적합은 최대 \(N \times \max(A_i) = 10^5 \times 10^9 = 10^{14}\)까지 커지므로, 합을 담는 변수와 입력 \(A_i\)를 모두 64비트 정수(long long)로 다뤄야 합니다. 뱉어낸 양 또한 같은 규모이므로 동일하게 처리합니다.
-
시간 복잡도: 서브태스크 3과 동일하게 \(O(N \log(\max A))\)이며, \(N = 2000\)에서도 매우 여유롭습니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, L;
ll a[100001];
ll eaten(ll k) {
ll sum = 0;
for (ll i = 1; i <= n; i++) sum += min(a[i], k); // 합이 10^14까지 → 반드시 long long
return sum;
}
int main() {
fastio
cin >> n >> L;
ll mx = 0;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
}
ll lo = 1, hi = mx, ansK = mx;
while (lo <= hi) {
ll mid = (lo + hi) / 2;
if (eaten(mid) >= L) {
ansK = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
ll spat = 0;
for (ll i = 1; i <= n; i++) spat += max(0LL, a[i] - ansK);
cout << ansK << endl;
cout << spat << endl;
return 0;
}
6. [서브태스크 5]: 추가 제한 없음
\(N\)이 최대 \(10^5\)까지 커지는 전체 제한입니다. 이진 탐색은 \(N\)에 선형으로만 비례하므로, 이미 충분히 빠른 알고리즘입니다. 정해와 동일한 접근으로 해결됩니다.
-
풀이: 앞선 이진 탐색 풀이를 그대로 사용합니다. \(K \in [1, \max(A_i)]\) 범위에서 \(\text{eaten}(K) \ge L\)을 만족하는 최소 \(K\)를 찾고, 그 \(K\)로 뱉어낸 양을 계산합니다. 단조성 덕분에 추가 자료구조 없이도 최적의 시간 복잡도를 달성합니다.
-
시간 복잡도: \(O(N \log(\max A))\)로, \(10^5 \times 30 \approx 3 \times 10^6\) 수준의 연산이라 제한 시간 내에 가뿐히 통과합니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, L;
ll a[100001];
ll eaten(ll k) {
ll sum = 0;
for (ll i = 1; i <= n; i++) sum += min(a[i], k);
return sum;
}
int main() {
fastio
cin >> n >> L;
ll mx = 0;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
}
ll lo = 1, hi = mx, ansK = mx;
while (lo <= hi) {
ll mid = (lo + hi) / 2;
if (eaten(mid) >= L) {
ansK = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
ll spat = 0;
for (ll i = 1; i <= n; i++) spat += max(0LL, a[i] - ansK);
cout << ansK << endl;
cout << spat << endl;
return 0;
}
7. 정해
-
풀이: \(\text{eaten}(K) = \sum_{i=1}^{N} \min(A_i, K)\)가 \(K\)에 대해 단조 증가한다는 성질을 이용한 매개변수 탐색(이진 탐색)이 정해입니다. "\(\text{eaten}(K) \ge L\)인가?"라는 판정 문제는 단조성을 가지므로, 답이 거짓인 영역과 참인 영역의 경계를 이진 탐색으로 찾으면 그것이 곧 최소 \(K\)입니다. 탐색 구간은 \(K \in [1, \max(A_i)]\)로 충분한데, \(K\)가 \(\max(A_i)\) 이상이면 모든 풀을 다 먹는 것과 같아 더 키울 의미가 없기 때문입니다(\(K\)가 존재한다는 조건이 보장됩니다). 최소 \(K\)를 확정한 뒤, 뱉어낸 풀의 총량 \(\sum_{i=1}^{N} \max(0, A_i - K)\)을 다시 한 번 계산해 함께 출력합니다. 누적합이 \(10^{14}\) 규모까지 커지므로 모든 합산 변수를 64비트(long long)로 두는 것이 정답의 마지막 조건입니다.
-
시간 복잡도: 판정 함수 \(\text{eaten}\)이 \(O(N)\), 이진 탐색 반복이 \(O(\log(\max A))\)이므로 전체 \(O(N \log(\max A))\)에 동작하여 가장 빠르고 안정적입니다.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define m2(x) ((x) << 1)
#define d2(x) ((x) >> 1)
#define endl "\n"
#define sp " "
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll n, L;
ll a[100001];
// K개를 한계로 둘 때 알파카가 먹는 풀의 총량
ll eaten(ll k) {
ll sum = 0;
for (ll i = 1; i <= n; i++) sum += min(a[i], k);
return sum;
}
int main() {
fastio
cin >> n >> L;
ll mx = 0;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
}
// eaten(K) >= L 을 만족하는 최소 K 를 이진 탐색
ll lo = 1, hi = mx, ansK = mx;
while (lo <= hi) {
ll mid = (lo + hi) / 2;
if (eaten(mid) >= L) {
ansK = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
// 그때 뱉어낸 풀의 총량
ll spat = 0;
for (ll i = 1; i <= n; i++) spat += max(0LL, a[i] - ansK);
cout << ansK << endl;
cout << spat << endl;
return 0;
}
실버 II