1654번

1654번 - 랜선 자르기

이분 탐색에 대해서 종만북으로 한번 보고 풀어본 문제.

만약 내가 이 문제가 이분탐색 문제라는 걸 몰랐다면 풀 수 있었을까? 이런 고민을 많이 한다.

이분 탐색도 결국은 주어진 범위 내에서 해가 있을 때, 완전 탐색을 좀 빠르게 하는 방식? 이라고 나는 이해했다..

앞으로 몇 문제를 더 풀어보면서 익혀야겠다.

decision() 함수를 통해 결정 문제로 바꾸고, 이분탐색을 통해 최적값을 찾도록 하였다.

문제에서 실수 2가지

1. 처음에 high 값을 vector.back() 으로 넣었는데 , 이러면 만약 답이 high 값이 될 경우에는 lo 가 high 에 막혀서 못 올라가는 경우가 생겼다.

   

   그래서 high 값을 vector.back() + 1값으로 바꿔주었다.

   마찬가지로, 물론 이 문제에서는 오류가 없었지만, lo 값도 0이 아닌 -1로 바꿔줘야 한다는 걸 깨달았다.

2. 랜선의 크기가 int 형을 넘을 수 있다는 점을 생각해내지 못해서 실수가 있었다. 이건 종종 있는 일이므로 더욱 조심할 것.

   변수형을 생각없이 습관적으로 사용하는 버릇을 조금 고칠 필요가 있다. 

   

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
bool decision(const vector<long long> &v, long long mid, int n)
{
    int ans = 0;
    for (int i = 0; i<v.size(); i++)
    {
        ans += (v[i] / mid);
    }
    return ans>=n;
}
 
int main()
{
    int N, K;
    vector<long long> v;
 
    cin >> K >> N;
    for (int i = 0; i < K; i++)
    {
        long long tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
 
    sort(v.begin(), v.end());
    
    long long lo = -1;
    long long high = v.back() + 1;
    long long mid;
 
    for (int i = 0; i < 100; i++)
    {
        mid = (lo + high) / 2;
 
        if (decision(v,mid,N))
        {
            lo = mid;
        }
        else
        {
            high = mid;
        }
    }
 
    cout << lo << endl;
 
    return 0;
}