algospot 수강 철회 (문제 ID: WITHDRAWAL) C++

알고스파ㅅ 문제 링크: https://www.algospot.com/judge/problem/read/WITHDRAWAL

algospot.com :: WITHDRAWAL

각 과목의 수강인원과 본인의 중간고사 등수가 주어지고, k개의 과목만을 남겨놓고 수강철회를 할 수 있다.

이때 얻을 수 있는 최소누적등수를 구하는 문제이다.

직관적으로 보면 r[i]/c[i]가 높은 순으로 수강철회를 하는 그리디 방식을 취하면 될것 같지만, 값을 몇번만 대입해봐도 이런 방식으로는 원하는 값을 얻을 수 없다는걸 알 수 있다.

해결책으로는 이분법을 사용하여 누적등수를 대입해가면서 sum(해당누적등수*c[i] - r[i])가 0이상인지 확인하는 방식으로 누적등수의 범위를 좁혀가면 된다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/12.%20DecisonProblem/WITHDRAWAL.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1