알고스팟 - 수강철회 (WITHDRAWAL)

문제 : https://algospot.com/judge/problem/read/WITHDRAWAL 

이 문제에서 n개의 수강과목이 주어지고, 이 중에서 k개의 수강과목을 선택하여 누적등수를 높이고자 합니다. 이 문제를 해결하는 가장 단순 무식한 방법은 n개의 과목 중에서 모든 경우의 k개의 과목을 선택하여 가장 낮은 값을 가지는 누적 등수 값을 찾는 것입니다. 즉, n개 중에서 k개를 선택하는 경우의 수만큼 검사를 해야 합니다. 

그 공식은 위와 같이 나타낼 수 있는데, 문제에서 n의 값이 1000까지 가능하다고 하기 때문에, 예를 들어, n=1000이고, k=10일 경우, 모든 가능한 경우의 수는 다음과 같이 상당한 값을 가지게 됩니다.

따라서, 단순 무식한 방법으로는 절대 결과를 얻을 수 없다는 것을 알 수 있습니다. 이와 같이 경우의 수가 매우 많을 경우에는 정확한 답을 얻지 못하지만 짧은 시간 내에 답에 거의 가까운 값을 얻어내는 추정 기법을 사용할 수 있습니다. 문제에 제시된 바와 같이, 우리는 n개의 수강과목 중에 중간고사 누적등수를 가장 낮게 만들 수 있는 k개의 수강과목만 선택하면 됩니다. 그리고, k개의 수강과목을 선택하여 얻은 중간고사 누적등수 값은 0~1사이의 실수 값을 가집니다. 여기서 값이 0이면 모든 학생 중에서 가장 등수가 높다는 것을 의미하고, 1은 가장 낮다는 것을 의미합니다. 중간고사 누적등수 값을 p라고 할 때, 우리가 선택한 k개의 과목에 대하여 다음의 공식이 성립합니다.

즉, i번째 수강과목의 전체학생 수를 추정 값인 p와 곱하면 등수가 나오는데, 그 등수와 실제 본인의 등수 차이 값이 0이면 p가 정확하다고 할 수 있으며, 결과가 양수면 p가 높게 추정되었다는 것을, 그리고 결과가 음수라면 p가 낮게 추정되었다는 것을 의미합니다. 이러한 원리를 이용하여 우리는 p의 범위 중간 값인 0.5부터 가정하여 n개의 과목들에 대하여 f(i,p)를 계산하여 상위 k개의 과목의 합이 0보다 큰 경우 p의 값을 최대값으로 지정하고, 합이 0보다 작을 경우 현재 p의 값을 최소값으로 지정하여 같은 작업을 반복수행합니다. 그러면 궁극적으로 f(i,p)는 k개의 과목에 대해 0에 가까운 값을 가지게 됩니다.

예를 들어 설명하겠습니다. 다음과 같이, 수강과목 네 개가 있고 각각의 수강인원과 등수가 주어졌다고 가정하겠습니다. 그러면 각 수강과목에 대해 f(i,0.5) 값을 계산합니다.

네 개의 f값 중에서 상위 두 개는 과목3과 과목4입니다. 그리고 이들을 더하면 2.5가 되고 이는 양수이므로 p값을 0.5에서 0.25로 낮춰줄 수 있습니다.

마찬가지로, p=0.25일 때 각 과목에 대한 f값을 계산하면 다음과 같이 나타낼 수 있으며, 이 중에서 상위 k개의 합은 -2.25로 0보다 작기 때문에 p의 값을 0.25에서 0.125를 증가시킨 0.375에 대하여 같은 작업을 수행합니다. 보시다시피 p의 값을 특정 짓고 끝내는 방식이 아니라 p를 증가시키거나 감소시키는 방식을 반복하기 때문에 끝이 나지 않는다는 것을 알 수 있습니다. 이와 같은 추정방법은 기본적으로 작업을 많이 반복할수록 더 정확한 값이 나오지만 문제에서 10의 -7승 이하의 숫자는 무시해도 된다고 하였으므로 위의 작업을 100번 정도 반복하면 0.3333333333이라는 정답을 얻을 수 있게 됩니다.