WITHDRAWAL (상, p. 458)
문제#
어떻게 풀었나?#
처음에는 그리디 방식으로 접근했다. 그리고 그렇게 풀어서 AC를 받았는데, 알고보니 알고스팟 채점데이터가 약해서 AC를 받은 것이고 이 문제는 절대 그리디로 풀 수 없는 것을 알게 됐다.
정해 - Parametric Search (Binary Search)#
먼저 정해인 parametric search 풀이법에 대해서 얘기하면 다음과 같다.
이 문제는 전형적인 “비율 최소화/최대화” 문제로 목표 값 $x$를 정해놓고
“누적 등수(accumulativeRank)를 $x$이하로 만들 수 있나?”
를 판정하면서 이를 만족하는 최소의 $x$값을 찾으면 된다.
판정식은 아래와 같이 바꿀 수 있는데, 이 방법이 문제를 푸는 핵심이다. 비율 최대화라는 비선형 문제를 x값 결정문제로 변경하여 선형화 시키는 것이다.
$$ \frac{\sum_{i=0}^{n-1}{r_i}}{\sum_{i=0}^{n-1}{c_i}} ≤ x ⇔ x\sum_{i=0}^{n-1}{c_i}-\sum_{i=0}^{n-1}{r_i}≥0 ⇔ \sum_{i=0}^{n-1}{(xc_i-r_i)}≥0 $$그러면 최종 식 $\Sigma{(xc_i-r_i)}≥0$ 을 만족하도록 최소 k개의 과목$(r_i,c_i)$을 택하면 된다. 만약 그러한 과목을 k개만큼 선택할 수 없다면 $x$값을 늘려서 확인해보면 되고, k개만큼 선택할 수 있다면 $x$값을 더 줄일 수 있는지 확인해보면 될 것이다.
오답 - Greedy#
$$ \sum_{i=0}^{n-1} r_i = R, \sum_{i=0}^{n-1}c_i = C $$이라 할 때, 여기서 $\frac{R}{C}$를 줄일 수 있는 $\frac{r_i}{c_i}$를 찾는다 하면, 아래의 식을 만족해야 할 것이다.
$$ \frac{R-r_i}{C-c_i} ≤ \frac{R}{C} $$해당 부등식을 변형하면 아래와 같은 부등식을 얻을 수 있다.
$$ ⇔ RC-r_iC ≤ RC-Rc_i $$$$ ⇔ \frac{r_i}{c_i} ≥ \frac{R}{C} $$즉, 현재의 $\frac{R}{C}$이상인 $(r_i, c_i)$를 택하면 된다.
그러면 반복문을 돌면서 현재의 $\frac{R}{C}$값을 가장 크게 줄일 수 있는 과목$(r_i, c_i)$을 택하고 이를 수강 철회하여 누적 등수를 갱신하는 식으로 문제를 풀면 정답이 될 수 있지 않을까?
원래 이런 그리디 방식을 생각하는게 증명이 어려워서 일단 구현을 해서 코드를 제출했는데 AC를 받아버렸다. 하지만 이는 앞서 말했다시피 틀린 풀이법이다. 왜냐면, 어떤 과목을 수강신청하기로 선택했냐에 따라 다른 과목을 선택하는 가치가 항상 바뀌기 때문이다. 그래서 지금은 수강철회를 하는게 손해인 상황($\frac{r_i}{c_i} < \frac{R}{C}$)이라 철회할 수 없는데, 다른 과목들을 수강철회한 뒤엔 방금 전 손해였던 과목을 꼭 철회하는 것이 최적의 해가 되는 경우가 생긴다. 아니면 그 반대의 상황일 수도 있다. 누적 등수가 가장 많이 줄어들어 수강철회 대상 과목으로 선택했는데, 그 이후에 선택하는 다른 과목들에 의해 누적 등수는 변경되기 때문에 앞서 선택한 수강철회 과목이 수강신청을 그대로 유지해야 하는 과목이 될 수도 있는 것이다.
이와 같은 반례는 아래와 같다.
1
6 3
1 4 5 8 3 3 5 7 1 6 5 8정답은 0.3846153846이 되어야 하는데, 그리디로 풀게되면 0.3888888889이 나온다.
이는 그리디 방식에선 (3,3)을 먼저 제거하는 것이 누적 등수 값을 가장 크게 낮춰서 제일 먼저 선택되어 수강철회 되지만, 실제 정답에는 (3,3)을 남겨야 한다. (정답은 (1,4), (3,3), (1,6)을 선택하는 것이 된다.)
정답 코드#
#include <bits/stdc++.h>
using namespace std;
int n,k;
int r[1001], c[1001];
vector<double> v;
bool Judge(double x) {
v.clear();
for(int i=0; i<n; i++) {
v.push_back(x*c[i]-r[i]);
}
sort(v.begin(), v.end());
double sum=0;
for(int i=n-k; i<n; i++) {
sum+=v[i];
}
return sum>=0;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int tc; cin >> tc;
while(tc--) {
cin >> n >> k;
for(int i=0; i<n; i++) {
cin >> r[i] >> c[i];
}
double lo=0, hi=1;
while(hi-lo>1e-14) {
double mid = (lo+hi)/2;
if(Judge(mid)) hi=mid;
else lo=mid;
}
printf("%.10lf\n", hi);
}
return 0;
}Comment#
아래의 코드는 틀렸음에도 불구하고 2026년 1월 25일 기준으로 Algospot OJ에서 AC를 받을 수 있다.
오답 - Greedy 코드#
#include <bits/stdc++.h>
using namespace std;
int r[1001], c[1001];
double val[1001];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int tc; cin >> tc;
while(tc--) {
int n,k; cin >> n >> k;
int rsum=0, csum=0;
for(int i=0; i<n; i++) {
cin >> r[i] >> c[i];
rsum += r[i];
csum += c[i];
val[i] = (double)r[i]/c[i];
}
double valsum = (double)rsum/csum;
int remain = n;
while (remain > k) {
double mn_tmp = valsum;
int mn_i = -1;
for (int i = 0; i < remain; i++) {
if(valsum <= val[i]) {
double tmp = (double)(rsum-r[i])/(csum-c[i]);
if(tmp - mn_tmp < 1e-12) {
mn_tmp = tmp;
mn_i = i;
}
}
}
if(mn_i == -1) break;
rsum -= r[mn_i];
csum -= c[mn_i];
valsum = (double)rsum/csum;
swap(r[remain-1],r[mn_i]);
swap(c[remain-1],c[mn_i]);
swap(val[remain-1],val[mn_i]);
remain--;
}
printf("%.10lf\n", valsum);
}
return 0;
}WITHDRAWAL 문제에서 알아야 할 것들#
1. 선형과 비선형의 정의#
선형#
각 선택의 기여도($w$)가 서로 독립적이고, 합치면 그냥 더해진다.
수식으로 보면 아래와 같다.
$$ f(S) = \sum_{i \in S} w_i $$- $S$: 선택한 원소의 집합
- 각 원소의 기여도($w_i$)는
- 다른 원소가 뭘 선택됐는지와 무관
- 순서에도 무관
비선형#
어떤 원소를 선택했냐에 따라 각 원소의 기여도가 변한다.
이와 같은 비선형의 사례를 수식으로 표현하면 다음과 같다.
$$ f(S) = \frac{\sum a_i}{\sum b_i} $$- 여기서 분모가 바뀌면 모든 원소의 기여도가 동시에 변한다. → 따라서 개별 항의 기여도를 분리할 수 없다.
2. 왜 이 문제는 비선형인가?#
$$ \text{cumulativeRank} = \frac{\sum r_i}{\sum c_i} $$여기서 i 하나의 “기여도”를 정의하려고 하면:
- i를 넣었을 때 효과는 다른 애들 합에 따라 달라짐
- i를 뺐을 때 효과도 현재 상태($\frac{R}{C}$) 에 따라 달라짐
즉, “이 과목은 나쁘다/좋다”를 고정된 숫자로 말할 수 없다.
3. 비선형을 선형 문제로 바꾸는 방법#
Parametric Search
“답이 x일 때 조건을 만족하는가?”를 묻는 문제를 Yes / No 판정 문제로 바꿔서 푸는 방법