강의로 돌아가기
khhan1993

동일한 코드를 제출했는데 채점 결과가 다릅니다.

동일한 코드에 대해서 다른 채점 결과가 나옵니다. (재채점을 위해 코드상에 주석을 삽입)
차이가 발생하는 부분은 효율성 5번 TC 이며 같은 코드에 대해서 어느 경우는 AC, 어느 경우는 TLE 가 발생합니다.

TLE 판정의 경우 어떤 경우는 아슬아슬하게 통과하고 어떤 경우는 아슬아슬하게 통과하지 못하는 경우가 발생하는 것을 지양해야 하는데 (달리 말하자면, 시간 제한이 1초라면 AC 를 받을 코드는 평균적으로 0.5초 이내에 끝나고, TLE 를 받을 코드는 적어도 3초 이상 걸려야 한다고 봅니다) 이 부분에 대해서 문제가 없는지 확인 부탁드립니다.

아래 코드는 90점 (효율성 2번, 5번 TC 에서 TLE 판정) 을 받은 코드입니다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <functional>
#include <limits>
#include <unordered_set>
#include <unordered_map>

using namespace std;

int solution(vector<int> budgets, int M) {
    sort(budgets.begin(), budgets.end());

    vector<int64_t> budget_sums(budgets.size());

    budget_sums[0] = (int64_t)budgets[0];
    for(auto i = 1; i < budgets.size(); i++) {
        budget_sums[i] = (int64_t)budgets[i] + budget_sums[i - 1];
    }

    if(budget_sums.back() <= (int64_t)M) {
        return budgets.back();
    }
    /*
    else if((int64_t)budgets.front() * (int64_t)budgets.size() >= (int64_t)M) {
        //cout << (M / (int)budgets.size()) << endl;
        //return (M / (int)budgets.size());
    }
     */

    int left = 0;
    int right = 100000;

    while(left <= right) {
        int mid = (left + right) / 2;

        int pos = (int)(upper_bound(budgets.begin(), budgets.end(), mid) - budgets.begin());
        int64_t tmp = (int64_t)((int64_t)mid * (int64_t)((int)budgets.size() - pos));
        if(pos > 0) {
            tmp = budget_sums[pos - 1] + (int64_t)(mid * (int)((int)budgets.size() - pos));
        }

        if(tmp <= (int64_t)M) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    return right;
}

그리고 아래 코드는 95점 (효율성 2번 TC 에서 TLE 판정) 을 받은 코드입니다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <functional>
#include <limits>
#include <unordered_set>
#include <unordered_map>

using namespace std;

int solution(vector<int> budgets, int M) {
    sort(budgets.begin(), budgets.end());

    vector<int64_t> budget_sums(budgets.size());

    budget_sums[0] = (int64_t)budgets[0];
    for(auto i = 1; i < budgets.size(); i++) {
        budget_sums[i] = (int64_t)budgets[i] + budget_sums[i - 1];
    }

    if(budget_sums.back() <= (int64_t)M) {
        return budgets.back();
    }


    int left = 0;
    int right = 100000;

    while(left <= right) {
        int mid = (left + right) / 2;

        int pos = (int)(upper_bound(budgets.begin(), budgets.end(), mid) - budgets.begin());
        int64_t tmp = (int64_t)((int64_t)mid * (int64_t)((int)budgets.size() - pos));
        if(pos > 0) {
            tmp = budget_sums[pos - 1] + (int64_t)(mid * (int)((int)budgets.size() - pos));
        }

        if(tmp <= (int64_t)M) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    return right;
}

두 코드 간 차이는 주석이 있냐 없냐 밖에 없습니다.

1 개의 답변
Demi

안녕하세요.
Cpp 언어에서 일부 효율성 테스트케이스의 시간 제한이 restrict 하다는 의견이 많아, Cpp 언어 기준 시간 제한을 완화하였습니다.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.