(C++) - 백준(BOJ) 14627번 : 파닭파닭

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

14627번: 파닭파닭

이분탐색 문제였습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

 s : 파의 개수

 c : 주문된 파닭 수

 ans : 정답(라면에 넣을 파의 양)

 greenOnion : 파의양을 입력받을 일차원 배열을 선언합니다.

 

📔 풀이과정

 파닭에 넣을 파의 양을 mid로 두어 이분탐색을 시행합니다.

 

 1. mid는 0 ~ s까지의 모든 i에 대해 greenOnion[i] / mid의 합을 구하면 최소 처리할 수 있는 파닭주문의 수가 됩니다. 이를 최소한으로 넘는 최댓값 r을 찾습니다.

 

 2. 이 합은 임시변수 cnt에 넣어 만약 cnt가 c미만이면 파의 양을 줄여서 cnt를 늘려야 하므로 r = mid - 1이됩니다.

 

 3. cnt가 c이상이면 파의 양을 늘려 cnt를 줄여도 되기 때문에 l = mid + 1이 됩니다.

 

* cnt 가 c보다 1부족할 때까지 r = mid - 1이므로 r을 반환해줘야 최소한 cnt >= c가 될 수 있습니다.

 

 4. 시장에서 사온 모든 파의 양을 ans에 더해줍니다. 이분탐색의 결과는 amount라는 long long형 변수에 저장합니다.

 

📔 정답출력

라면에 넣을 파의 양은 시장에서 사온 파의 양 - amount * c가 됩니다. 이를 출력합니다.

* amount * c의 경우 amont가 10억만 되어도 int범위를 초과하므로 long long으로 선언해야 정확한 답을 출력할 수 있습니다. 

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll s, c, ans, greenOnion[1000001];

ll binarySearch(){
    ll l = 1;
    ll r = 0x3f3f3f3f;
    while(l<=r){
        ll cnt = 0;
        ll mid = (l + r) / 2;
        for(int i = 0; i < s; i++) cnt += greenOnion[i] / mid;
        if(cnt < c) r = mid - 1;
        else l = mid + 1;
    }
    return r;
}

int main(){
    cin >> s >> c;
    for(int i = 0; i < s; i++) cin >> greenOnion[i];
    ll amount = binarySearch();
    for(int i = 0; i < s; i++) ans += greenOnion[i];
    cout << ans - amount * c << '\n';
}

 

📕 TestCase

9 8
1 5 3 1000000000 6 29 13 2 15
답 : 74

 

4 4 
20 20 20 20
답 : 0

 

3 6
100 100 100
답 : 0

 

* 질문게시판

3 5
100 100 100
답 : 50