1645_랜선 자르기

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

1654번: 랜선 자르기

이분검색을 이용하여 랜선을 자르는 문제이다. 다합쳐서 나누기를 하는 방법을 처음 생각해봤는데 제대로 된 답이 안나왔다. 그렇다면 기존의 랜선 중 하나를 정해서 이분 탐색을 이용해 수를 찾아서 정답을 도출하는 방법이 생각이 났다. 몇가지 오류가 있어서 사람들꺼 참조해보니 논리는 잘 되었지만 몇가지 부분에서 잘못된 것이 있었다.   
* 내가 짜놓은 코드는 첫번째로 만족하면 바로 빠져나가서 제대로 된 답을 도출하지 못하여서 `max_value = max(max_value, mid);`로 수정해주었다.   
* 다음은 left를 0으로 초기화 시켰는데 0으로 초기화하면 제대로 된 답이 나오지 못했다. 왜냐하면 0로 나눠줘야 하는 경우의 수가 생겼기 때문이다. 0으로 나누는 것은 에러가 뜬다. 그러므로 left를 1로 초기화 해주었다.   

생각하는 과정

 

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
int wires[10001];
int main(void){
    int n, k, val;
    long long left, right, mid, sum, max_value;
 
    val = 0;
    cin >> k >> n;
    for(int i = 0; i < k; i++){
        cin >> wires[i];
        val = max(wires[i], val);
    }
    left = 1, right = val; max_value = 0;
    while(left <= right){
        mid = (left + right) / 2;
        sum = 0;
        for(int i = 0;i < k ; i++)
            sum += (wires[i] / mid);
        if(sum < n)
            right = mid - 1;
        else if(sum >= n){
            left = mid + 1;
            max_value = max(max_value, mid);
        }
    }
    cout << max_value;
}