[결정 문제] [시간 초과] WITHDRAWAL 수강 철회

1. 최적 문제

 

 n개의 강의 중에서 k개이상의 강의만 남겨놓고 철회할 때

최소 누적 등수를 구하는 문제이다.

 

이것은 k개 까지 하나 하나 철회해보면서 누적등수를 계산하고 그 중에서

최소값을 구하는 최적화 문제이다.

 

이 문제를 결정문제로 변형해보자

 

2. 결정 문제

 

isOkay(r) = r의 누적등수가 주어졌을 때 이것보다 작은값이 있는가?

 

위와 같은 식을 토대로 함수를 작성해 보았다.

 

isOkay는 k개 까지 모든 경우를 세서 주어진 누적등수보다 작은 값이 나오면 true

작은 값이 나오지 않을 경우 false를 반환한다.

 

 

하지만 이 함수는 최악의 경우 2^1000 개를 카운트하므로 당연히 제출한 코드는 시간 초과를 내뿜었다.

 

이전 꺼랑 비교해서 더 큰값이 나올 경우 가지치기하려는 생각도 해봤지만 답을 구하는것과 상관이 없었다.

 

 

int T, N, K;
std::vector<std::pair<int, int>> lec;
//r c
 
bool isOkay(double R, int current, int select, int rsum, int csum)
{
    if(select < K) return false;
    if(R >= (double)rsum/csum) return true;
    if(current < 0) return false;
 
    if(isOkay(R, current-1, select-1, rsum - lec[current].first, csum - lec[current].second)) return true;
    if(isOkay(R, current-1, select, rsum, csum)) return true;
    
    return false;
}
 
double optimize()
{
    double lo = 0, hi = 1.0;
    int rsum = 0, csum = 0;
    std::sort(lec.begin(), lec.end());
    for(int i = 0; i < N; i++)
    {
        rsum += lec[i].first;
        csum += lec[i].second;
    }
 
    for(int i = 0; i < 100; i++)
    {
        double mid = (hi + lo)/2.0;
        if(isOkay(mid, N-1, N, rsum, csum)) hi = mid;
        else lo = mid;
    }
    return hi;
}

 

 

3. 수학식을 바꿔보자

 

책에서는 비율을 구하는 대신에 분모를 없애 문제를 간단하게 만들었다.

 

sum(r)/sum(c) <= x

 

sum(r) <= x * sum(c)

 

0 <= sum(x * ci) - sum(ri)

 

0 <= sum(x * ci - ri)

 

즉 x*ci - ri 를 모두 구한다음

 

가장 큰것들 중 k~n개를 뽑아 더하면 0이상이 나오는가? 를 판단하면된다.

 

이것은 O(nlgn)만에 수행되어 이전 보다 엄청 빠르게 답을 내놓는다.

 

 

 

WITHDRAWAL