[C++] 백준 2512번: 예산 (멍청한 짓 하지 않기, 그래도 풀어서 기분 좋아)

문제

https://www.acmicpc.net/problem/2512

2512번: 예산

 

사실 이 문제 보자마자 초등 올림피아 2번 문제라길래 조금 충격 먹었다 ^^

요즘엔 초딩들도 실버문제는 가볍게 푸는 구나

반면에 가볍게 풀지 못한 나의 풀이다

 

 

 

이 조건을 반영해야 하기 때문에 내가 생각한 아이디어는 다음과 같다.

 

(요청 금액의 배열 v를 내림차순 정렬)

1. 요청한 금액 총합이 예산보다 작거나 같을 땐 v[0] 출력

2. 요청한 금액 총합이 예산보다 클 때

2-1. 예산과 요청금액 총합의 차이를 r이라고 할때, if( v[0] -r  >= v[1]) 이면  v[0]-r 출력

2-2. 그렇지 않을 때, (v[0]+v[1] -r)/2 >= v[2] 이면 (v[0]+v[1] -r)/2 출력

2-3. 그렇지 않을 때, (v[0]+v[1]+v[2] -r)/3 >= v[3] 이면 (v[0]+v[1]+v[2] -r)/3 출력

 

의 아이디어를 통해 아래 코드를 짰다.

//
//  main.cpp
//  백준 10815번
//
//  Created by 신지원 on 2022/07/15.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);cin.tie(0);
    
    int n,m,sum,res;
    cin >> n;
    
    vector<int> v;
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        v.push_back(a);
        sum += a;
        
    }
    sort(v.begin(),v.end(),greater<int>()); //배열을 내림차순 정렬 해준다.
    
    cin >> m;
    
    if(sum <= m) cout << v[0] << "\n";
    // 국가 예산이 요청금액의 총합보다 크거나 같다면 가장 큰 첫번째 값을 출력한다.
    
    else{
    // 그렇지 않을때
        
        res = sum - m;
        int i,count,ssum,rres;
        i = 0; count = 1; ssum = v[0]; rres = 0;
        
        while(1){
            rres = (ssum-res)/count;
            if( rres >= v[i+1]){
                cout << rres << "\n";
                break;
            }
            else{
                i++; count++;
                ssum += v[i];
            }
        }
    }
    return 0;
}

 

테스트 값 잘나와서 흐뭇하게 정답 돌렸는데 fail ^^

다른 분들 참고해도 넘 졸려서 그런지 잘 모르겠다 내일 다시 글쓰자

 

 

++한 3일만에 추가글

 

이건 이분탐색으로 돌렸어야 한다. 이틀동안 졸린 눈 비비며 풀다가 안되겠다 싶어 뽝 풀었다!

지난 날에 다른 분들 참고했어서 그런지 훌쩍훌쩍 잘 풀었다.

 

//
//  main.cpp
//  백준 2512번
//
//  Created by 신지원 on 2022/07/20.
//

#include <iostream>
#include <vector>
#include <algorithm>
#define max(a,b) ? a > b;

using namespace std;

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0);cin.tie(0);
    
    int n,m;
    int sum = 0;
    cin >> n;
    
    vector<int> v;
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        v.push_back(a);
        sum += a;
        
    }
    
    cin >> m;
    
    
    sort(v.begin(),v.end());
    
    if(m >= sum){
        cout << v[n-1] << "\n";
        return 0;
    }
    
    int start, end, mid, total, res;
    start = 0; end = v[n-1];
    res = 0;
    
    while(start <= end){
        mid = (start + end)/2;
        total = 0;
        
        for(int i=0;i<n;i++){
            total += min(v[i],mid); //point 1
        }
        
        if(total <= m){
            res = mid;
            start = mid +1; //point 2
        }
        
        else if(total > m){
            end = mid - 1;
            
        }
        
        
    }
    cout << res << "\n";
    
    return 0;
}

 

이렇게 풀었고 멍청했던 나의 멍청점을  point 1, 2 로 표시해두었다.

1번은 왜 min 을 생각하지 못하냐는 것이다. v[i]-(v[i]-mid) 같은 생각을 하였다 정말 바보, 그래봤자 mid 인데

앞으론 멍청하게 굴지 않겠다.

 

point 2

 total <= m이 되도 끝나면 안된다. 우리는 "정해진 총액 이하에서 가능한 한 최대의 총 예산을" 구해야하기 때문이다.

후 바보 멍청이 저걸 몰라서 total, ttotal 을 두개로 해서 풀었더니 완전히 꼬여버렸었다. 

만약 total 이 ttotal 보다 크다면~ ttotal = total 이런 뉘앙스의 멍청한 짓을 헀다. 그냥 돌려주면 될 것을,,,

후 그래도 삼일에 걸쳐 예산 문제를 끝냈으니 다른 문제도 얼른얼른 풀고 dfs bfs 를 풀어야 겠당!