백준, BOJ, 2805번, 나무자르기 : C++ [CPP]

 

우선 숫자가 큰 문제이다.

뭔가 크다.

어렵진 않았지만..

그냥 오랜만에 푸니까 감이 안왔다.

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

 

---

 

시간초과 될 것을 알면서도

brute force로 해봤다.

#include <iostream>

using namespace std;

int N,M;
int maxi = 0;
int sum;
int arr[1000001];



int main(){
    cin >> N >> M;
    for(int i = 1; i<=N; i++){
        int a;
        cin >> a;
        arr[i] = a;
        if(a>=maxi){
            maxi = a;
        }
    }
    
    maxi--;
    while(1){
        sum = 0;
        for(int j = 1; j<=N; j++){
            int temp = arr[j] - maxi;
            if(temp>0) sum += temp;
        }
        
        if(sum>=M){
            break;
        }
        maxi--;
    }
    
    cout << maxi;
}

 

그렇다면 Sorting 해서 최대한 덜..

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

using namespace std;

int N, M;
int maxi = 0;
int sum;
vector <int> vec;


int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        vec.push_back(a);
        if (a >= maxi) {
            maxi = a;
        }
    }

    maxi--;
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    while (1) {
        sum = 0;
        for (int j = 0; j < N; j++) {
            int temp = vec[j] - maxi;
            if (temp > 0) {
                sum += temp;
            }
            else {
                break;
            }
        }

        if (sum >= M) {
            break;
        }
        maxi--;
    }

    cout << maxi;
}

 

음.. 그렇다면 실제로 숫자 접근 중 가장 빠른..

이분 탐색을 이용해서 답에 접근..

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

using namespace std;

long long N, M;
int maxi = 0;
long long sum;
vector <int> vec;
int ans;




int main() {
    cin >> N >> M;
    for (int i = 0; i <N; i++) {
        int a;
        cin >> a;
        vec.push_back(a);
        if (a >= maxi) {
            maxi = a;
        }
    }

    int left = 0;
    int right = maxi;


    while (left <= right) {
        int mid = (left + right) / 2;
        sum = 0;
        for (int j = 0; j < N; j++) {
             if (mid < vec[j]) sum += vec[j]-mid;
        }
        if (sum >= M) {
            if(ans<mid){
                ans = mid;
            }
            left = mid + 1;

        }
        else {
            right = mid - 1;
        }
    }
    cout << ans;
}

 

임의의 숫자를 접근할 때에는

순차적으로 접근하기 보다는 이분 탐색으로 접근하는 것이 훨씬 효율적이라는 것을 알고 있었지만..

바로 생각이 안났다..ㅠ

그리고 숫자가 크면 int로 선언하기보다는 그냥 long long으로 하자..

오류가 덜 생긴다.