HyunwooAlpaca
실버 II
2026-05-26 08:43
A00002
알파카컵 1회: B - 알파카 농장
레이팅
의견: 1
설명
농장에 사는 알파카는 \(N\)일동안 총 매일 \(A_i\)개의 풀을 먹는다.
그런데, 알파카는 \(K\)개 초과의 풀을 먹을경우 풀을 \(K\)개가 될때까지 뱉어낸다.
알파카가 풀을 뱉어내는걸 보기 싫었던 농부 A씨는 알파카의 위장을 조정해 알파카가 \(N\)일동안 \(L\)개이상의 풀을 먹게 하고 싶어한다. 농부 A씨를 위해 \(K\)의 값이 최소일때 알파카가 풀을 뱉어낸 양을 구하자.
제약
\(1 \le N \le 10^5\)
\(1 \le A_i \le 10^9\)
\(1 \le L \le 10^9\)
\(1 \le K \le 10^9\)
모든 변수는 정수다.
(\(K\)는 항상 존재한다.)
입력 형식
첫번째 줄에 \(N\)과 \(L\)를 입력 받는다.
그 다음 줄엔 \(A_i\ (1\le i\le N)\)을 입력 받는다.
출력 형식
첫번째 줄에 \(K\)를 출력한다.
그 다음줄에 알파카가 풀을 뱉어낸 양을 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 1점 | \(A_1 + \cdots + A_N = L\) |
Subtask 2 | 12점 | \(1 \le N \le 20\) |
Subtask 3 | 21점 | \(1 \le N \le 500\) |
Subtask 4 | 25점 | \(1 \le N \le 2000\) |
Subtask 5 | 41점 | 추가 제한 없음 |
예제 1
입력
5 17
2 9 8 4 3출력
4
9힌트
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
힌트 1
로그인하고 잠금 해제 · 10 🪙
힌트 2
로그인하고 잠금 해제 · 20 🪙
문제 정보
태그
해설
알파카컵 1회: B - 알파카 농장
알파카컵 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;
}
평가 및 의견
알파카컵 1회: B - 알파카 농장
개요
티어 투표 분포
실버 II
1
Log in to rate problems.
개별 의견
HyunwooAlpaca
실버 II
2026-05-26 08:43
풀이 제출
알파카컵 1회: B - 알파카 농장
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기