사탕 가방

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXdHxTNqC2IDFAS5

SW Expert Academy

 

이진 탐색을 사용하는 문제이다.

l과 r에는 가방 개수가 들어간다.

 

초기값은

l = 0, r은 사탕 배열의 최대값 + 1

이렇게 해야

check(l) = True

check(r) = False

 

사탕 배열의 값을 가방 개수로 나눈 값이

m이상이 되도록 만들자.

check() 함수는 나누기를 하는데?

0으로 나눠도 됨? 근데 쩔수가 없다..

극한으로 생각을해서 m 이상이 된다고 하자.

 

T T T T F F ...

left가 정답이 되는 결정 문제이다.

 

left가 될 수 있는 값이 사탕 배열의 최대값까지 가능하므로

right = dae + 1;

 

근데 문제는 정확히

가방 안에 정확히 M개의 사탕이 들어 있어야 한다.

 

경계값을 제대로 설정했다면

전혀 문제될 것이 없다.

 

 

<소스 코드>

#include <iostream>
#include <cstring>
 
using namespace std;
 
int main()
{
    int test;
    cin >> test;
 
    long long arr[104];
 
    // 사탕 최대 개수
    long long dae = 0;
 
    for (int t = 1; t <= test; t++) {
        memset(arr, 0, sizeof(arr));
        dae = 0;
 
        int n;
        long long m;
        cin >> n >> m;
 
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
 
            if (dae < arr[i])
                dae = arr[i];
        }
 
        // 이진 탐색
        // 사탕 가방의 개수가 기준
        // 사탕이 가방에 m개 이상 들어있게 만들자
        // T T T F F 인 결정 문제
        long long left = 0;
        long long right = dae + 1;
        // check(l) True
        // check(r) False
        long long ans = 0;
 
        while (left + 1 < right) {
            long long mid = (left + right) / 2;
 
            // 사탕 비교
            long long tmp = 0;
 
            for (int i = 0; i < n; i++)
                tmp += arr[i] / mid;
 
            if (tmp >= m)
                left = mid;
            else
                right = mid;
        }
 
        cout << '#' << t << ' ' << left << '\n';
    }
}