🚀 [WITHDRAWAL] 문제 📈📈📈📈😊
이번 학기에 욕심을 부려 학점 초과신청을 한 백준이는 중간고사 성적을 보고 한숨을 토할 수밖에 없었습니다. 다음 학기 장학금을 받을 만큼 성적이 잘 나오지 않았기 때문입니다. 이제 백준이에게 남은 희망은 다음 주의 수강 철회 기간 뿐입니다.
백준이네 학교에서는 장학금을 학생의 중간고사 등수와 기말고사 등수에 따라 배정합니다. 어떤 학생이 듣는 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 이하의 오차가 있는 답은 정답으로 인정됩니다.
🖱 입력 예제
3
3 2
1 4 6 10 10 17
4 2
4 8 9 12 3 10 2 5
10 5
70 180 192 192 1 20 10 200 6 102 60 1000 4 9 1 12 8 127 100 700
💻 출력 예제
0.5000000000
0.3333333333
0.0563991323
💎 전체 코드는 다음과 같습니다.
//
// WITHDRAWAL.cpp
// AALGGO
//
// Created by inhyeok on 2021/11/06.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("WITHDRAWAL.txt");
int n; // 수강하는 과목 수
int k; // 남겨야할 최소 과목 수
int studentNum[1000]; // i번째 과목 수강생 수
int classRank[1000]; // i 번째과목 등 수
/*
최소 누적등수(average)
누적등수 = sum(r[i])/sum(c[i])
누적등수가 <= average 인가 아닌가.
0 <= sum( average*학생수[i] - 등수[i])
*/
bool decision(double average){
// v[i] == x*r[i] - c[i]
vector<double> v;
double sum = 0;
for(int i=0; i<n; i++){
v.push_back(average*studentNum[i] - classRank[i]);
}
// 정렬하여 v 중 가장 큰것들을 고르기 위해
sort(v.begin(), v.end());
// k개 이상을 수강하는 것
for(int i=n-k; i<n; i++){
sum+=v[i];
}
return sum>=0;
}
// 확률은 0~ 1 이내의 숫자이기 떄문.
double optimize(){
double lo=0, hi = 1;
for(int i=0; i<100; i++){
double mid = (lo+hi)/2.0;
if(decision(mid)){
hi = mid;
}
else{
lo = mid;
}
}
return hi;
}
int main(){
int test_case;
fin >> test_case;
for(int test=0; test < test_case; test++){
fin >> n >> k;
for(int i=0; i<n; i++){
fin >> classRank[i] >> studentNum[i];
}
printf("%.8f\n", optimize());
}
}
Comments