[Algospot] 수강 철회 (문제 ID : WITHDRAWL)

문제

이번 학기에 욕심을 부려 학점 초과신청을 한 백준이는 중간고사 성적을 보고 한숨을 토할 수밖에 없었습니다. 다음 학기 장학금을 받을 만큼 성적이 잘 나오지 않았기 때문입니다. 이제 백준이에게 남은 희망은 다음 주의 수강 철회 기간 뿐입니다.

백준이네 학교에서는 장학금을 학생의 중간고사 등수와 기말고사 등수에 따라 배정합니다. 어떤 학생이 듣는 i번째 과목의 수강생 수가 ci라고 합시다. 그리고 이 학생의 i번째 과목 중간 고사 등수가 ri라고 하면, 이 학생의 중간 고사 누적 등수 cumulativeRank 는 다음과 같이 정의됩니다.

cumulativeRank = sum(ri) / sum(ci)

예를 들어 백준이가 수강생이 각각 150, 200, 15명인 3개의 과목을 듣는데, 각각 100, 10, 5등을 했다면 백준이의 누적 등수를 다음과 같이 계산할 수 있지요.

(100 + 10 + 5) / (150 + 200 + 15) = 115 / 365 = 0.315..

수강 철회를 하면 철회한 과목은 중간 고사의 누적 등수 계산에 들어가지 않게 됩니다. 다행히 백준이네 학교에서는 수강 철회를 해도 남은 과목이 k 개 이상이라면 장학금을 받을 수 있습니다. 백준이가 적절히 과목을 철회했을 때 얻을 수 있는 최소 누적 등수를 계산하는 프로그램을 작성하세요.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 T (T <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 백준이가 수강하는 과목의 수 n(1 <= n <= 1,000)과 남겨둬야 할 과목의 수 k(1 <= k <= n)가 주어집니다. 다음 줄에는 n 개의 정수 쌍 (ri,ci) 이 순서대로 주어집니다. (1 <= ri <= ci <= 1,000)

 

출력

각 줄마다 백준이가 얻을 수 있는 최소의 누적 등수를 출력합니다. 정답과 10-7 이하의 오차가 있는 답은 정답으로 인정됩니다.

---

최적화, 결정 문제중에 가장 까다로운 문제였다. 그말은 즉 decision 구현이 힘들었다는 말이다.

decision(x) 를 몇몇 과목을 철회해 누적 등수 x이하 될 수 있는가로 설정하면 Sum(R) / Sum(C) <= x가 된다. 이 때 식을 조작해서

0 <= Sum(x*C - R)로 바꿔준다. 모두 계산한 후 가장 큰 K개의 원소를 더한다. 이 값이 0보다 크면 true를 반환한다.

optimize는 -1e-9부터 1까지 범위의 실수에서 이분탐색으로 값을 줄여간다.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/WITHDRAWL.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

int T, N, K;
int R[1001];
int C[1001];

bool decision(double x)
{
	vector<double> v;
	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;
}

double optimize()
{
	double lo = -1e-9, hi = 1;
	for (int i = 0; i < 100; i++) {
		double mid = (lo + hi) / 2;
		//´©Àû µî¼ö mid¸¦ ÇÒ ¼ö ÀÖ³ª?
		if (decision(mid)) 
			hi = mid;
		else
			lo = mid;
	}
	return hi;
}

int main()
{
	cin >> T;
	while (T--) {
		cin >> N >> K;
		memset(C, 0, sizeof(C));
		memset(R, 0, sizeof(R));
		for (int i = 0; i < N; i++)
			cin >> R[i] >> C[i];
		cout << fixed << setprecision(10);
		cout << optimize() << endl;
	}
}