강의로 돌아가기
nedcrow

채점결과가 30점인데 코드 좀 살펴봐주세요.

문제가 [40,20,30,10]일 때, M=36 이면, 답은 9 로 설정했습니다.
풀이방법은

  1. 예산리스트를 크기순 정렬하고 [10, 20, 30, 40] ...

2.예산 요청액 합(total) > 예산한도(M) 경우만 진행했습니다.

  1. For문을 활용해서 가장 큰 수부터 가장 작은수 순서로 사용했습니다. (40 - > 10) 3-1. 만약 For문이 마지막까지 오면 예산한도를, 요청 도시 수로 나눴습니다. 그리고 For문은 종료합니다. (36/4=9) 3-2. 만약 부족한 예산(total-M)이 가장 큰 수와 다음 큰 수의 차이(dist)의 반복횟수배 보다 적거나 같으면, (100-36 <= (40-30)*For반복횟수) 3-2-1. 가장 큰 수에서 차액만큼 감소하고 출력했습니다. 그리고 for문을 종료합니다. 3-3. 그렇지 않으면 부족한 예산을 dist만큼 줄이고 계속 for문을 돌립니다. (64-10)

For문을 1회 마치며 부족한 예산이 줄어든 이유는 이후 배열을 가정하기 위해서입니다.
10, 20, 30, 40 -> 10, 20, 30, 30 또는 10, 20, 20, 20 -> 10, 10, 10, 10

위의 경우 10까지 비교해야해서 그냥 예산한도를 요청 도시 수로 나눈 것입니다.
만약 이 전에 부족한 예산이 비교대상 도시들의 수보다 작으면, 그러니까 '부족한 예산 < (30-20)*For반복횟수' 인데,

M을 75으로 가정하면, 부족 예산이 25 -> 15 -> 5으로 낮아지고,
비교금액은 101->102->10*3으로 커집니다. 여기서는 15<=20 에서 멈추겠네요.
그러면 비교대상인 30에서 부족예산을 감소하는데 반복횟수도 반영해야겠죠.
그래서 30만큼 요청하는 도시가 2개라고 가정하게 되었으니 30-(15/2) 입니다. 홀수는 +1해줘서 결과는 22입니다.

기본 문제나 몇몇 추가 문제는 잘 풀리는데 채점결과가 영 안좋네요. 시간초과도 있고요.
그리고 제가 설명하면서도 뭔가 방법이 복잡해 보이네요;
어떻게 수정하면 좋을지 의견 부탁드립니다~

끝까지 읽으신 분들은 정말 고생하셨고 감사드립니다!

작성중인 코드―solution.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> budgets, int M) {
    int total=0;
    int answer = 0;
    int dist=0;
    vector<int> temp = budgets;
    sort(temp.begin(),temp.end());

    for(int i; i<temp.size(); i++){
        total += temp[i]; //총 요청액
    }

    if(total > M){ //총 요청액이 상한액 이상이면
        dist = total-M; //요청액합과 한계액의 차이.        
        int limit=0; //가장 큰 수와 다음 수의 차이 합.
        for(int i=0; i< temp.size(); i++){
            if(i==temp.size()-1){answer=(int)M/temp.size(); break;}
            int b=temp.size()-1-i; //큰수 순서대로 index.
            int big =temp[b]; //가장 큰 수 순서대로.
            limit = (big-temp[b-1])*(i+1);  
            //printf("dist:%d, limit:%d",dist,limit);
            if(dist<=limit){//총액차가 limit보다 작으면..
                int minus=dist/(i+1);
                if(dist%(i+1)!=0){minus = minus+1;}
                answer = big- minus; 
                break;
            }
            else{ dist= dist - limit;}
        }
    }


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