[백준(BOJ)] 2512번 : 예산 - C++[CPP]

www.acmicpc.net/problem/2512

2512번: 예산

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 이분 탐색

 

---

⊙ 문제 접근 과정

 

내가 생각하는 이진 탐색에서 가장 중요한 포인트는 기준이다.

index로 기준 잡고 탐색할지, value를 기준으로 탐색할지 문제를 본 뒤 결정해야 한다.

 

이번 문제는 value를 기준으로 이진 탐색을 해야 한다.

기준을 잡았으면 시작 값과 끝 값을 정해주는 것도 굉장히 중요하다.

이 문제에서 시작 값은 0, 끝 값은 예산 요청에서 가장 큰 값으로 설정했다.

 

그리고 sum 변수를 만들어 중간값보다 작으면 sum에 더해주고 국가 예산의 총액과 비교하여 이진 탐색을 하였다.

 

1. n, m, budget 값 받기
2. budget 정렬
3. value를 기준으로 이진 탐색
4. result 출력

---

 

⊙ 문제 풀이

 

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

using namespace std;

int n,m;
vector<int> budget;

int main() {
    cin >> n;
    for(auto i=0;i<n;i++) {
        int x;
        cin>>x;
        budget.push_back(x);
    }
    cin>> m;

    sort(budget.begin(),budget.end());

    int start=0;
    int end= budget[n-1];
    int result,sum;
    
    while(start<=end) {
        sum=0;
        int mid = (start+end)/2;
        for(auto i=0; i<n;i++) {
            sum += min(budget[i],mid);
        }
        if(m>=sum) {
            result=mid;
            start=mid+1;
        }else {
            end=mid-1;
        }
    }

    cout << result;
}

 

---

⊙ 결과

 

 

---

 

 

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!