글 읽기 - 어떤 input에서 틀리게 나왔는지 알고 싶습니다.

ldg1291 6년 전 0

제가 문제를 잘못이해한건지.. 잘 모르겠네요 ㅜㅜ

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

vector <int> budget;
vector <int> gather;

int main(int argc, const char * argv[]) {
    
    int N;
    
    scanf("%d", &N);
    
    for(int i=0; i<N; i++) {
        int tmp;
        scanf("%d", &tmp);
        budget.push_back(tmp);
        if(i == 0)
            gather.push_back(tmp);
        else gather.push_back(gather[i-1] + tmp);
    }
    
    sort(budget.begin(), budget.end());
    
    int lim;
    
    scanf("%d", &lim);
    
    if(gather[gather.size()-1] <= lim) {
        printf("%d\n", budget[budget.size()-1]);
    } else {
        int res = 0;
        int all = 0;
        for(int i=0; i<N-1; i++) {
            int size = 0;
            int sumall;
            if(i == 0) {
                size = lim/N;
                sumall = size*N;
            } else {
                size = (lim-gather[i-1])/(N-i);
                sumall = gather[i-1] + size*(N-i);
            }
            if(size <= budget[i]) {
                res = max(sumall, res);
                if(res == sumall) {
                    all = max(budget[i-1], size);
                }
            }
        }
        
        printf("%d\n", all);
    }
    
    return 0;
}

zlzmsrhak 6년 전 0

반례입니다. 조금 더 구체적인 피드백을 받고싶으시면 알고리즘 설명을 작성해 주셔야 합니다.

2
10 1 
5

ldg1291 6년 전 0

감사합니다!!

알고리즘 설계가 아예 잘못된 것 같아 처음부터 다시 짰는데 여전히 안되네요

알고리즘은
budget에다가 예산들을 받고 정렬한 이후
gather에다가 예산들의 합들을 넣습니다.
그리고 gather의 마지막 값이 lim보다 작거나 같다면 budget중 가장 큰 값을 출력합니다.
아니라면
예산의 한계를
(전체 예산 - (i번째까지의 예산들의 합))/(전체 시 갯수 - i)로 두고
조건에 맞는지 확인합니다.

감사합니다.

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector <int> budget;
set <int> gather;

int main(int argc, const char * argv[]) {
    
    int N;
    
    scanf("%d", &N);
    
    for(int i=0; i<N; i++) {
        int tmp;
        scanf("%d", &tmp);
        budget.push_back(tmp);
    }
    
    sort(budget.begin(), budget.end());
    
    for(int i=0; i<N; i++) {
        if(i==0)
            gather.insert(budget[i]);
        else {
            gather.insert(*(--gather.end()) + budget[i]);
        }
    }
    
    int lim;
    
    scanf("%d", &lim);
    
    if(*(--gather.end()) <= lim) {
        printf("%d\n", budget[N-1]);
    } else {
        
        int limit = 0;
        
        int num = 0;
        
        int all = 0;

        int res = 0;
        
        for(set<int>::iterator i = gather.begin(); i!=gather.end(); i++) {
            num++;
            if(budget.size() != num && lim>(*i)) {
                limit = (lim-(*i))/(budget.size() - num);
            }
            if(limit > budget[num-1] && limit <= budget[num]) {
                int sum = (*i) + (int)limit*((int)budget.size() - num);
                all = max(all, sum);
                if(all == sum)
                    res = max(res, limit);
            }
        }
        
        printf("%d\n", res);
    }
    
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떤 input에서 틀리게 나왔는지 알고 싶습니다.

ldg1291 6년 전 0

zlzmsrhak 6년 전 0

ldg1291 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말