랜선 자르기 1654

문제

접근 방법

이분 탐색을 통해 푸는 문제이다.
하지만 어떤 식으로 접근해야 하는지는 몰랐다. (잘 안 풀어봐서 몰랐다) 처음에는 가장 큰 값을 잘라서 배열에 넣고 정렬하는 방식으로 해결하는 문제인 줄 알았다. 하지만 그런 방법으로 할 때 삼등분해야 할지 이등분해야 할지 구별이 안 되기에 불가능하다고 생각했다.
이분 탐색은 높은 값과 낮은 값의 인덱스를 조절해서 적절한 값을 찾는 것이다. 가장 큰 랜선의 길이와 가장 작은 랜선의 길이 (1cm) 사이에서 값을 찾는 것이라는 것으로 생각하고 풀면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int K, N, ret = 0;
    long long start, end = 0, mid;
    cin >> K >> N;
    vector<int> lines;
    for (int i = 0; i < K; ++i)
    {
        int line;
        cin >> line;
        lines.push_back(line);
        if (end < line)
            end = line;
    }
    start = 1;
    while (start <= end)
    {
        mid = (start + end) / 2;
        int sum = 0;
        for (int line : lines)
        {
            sum += (line / mid);
        }
        if (sum >= N)
        {
            start = mid + 1;
            if (ret < mid)
                ret = mid;
        }
        else
        {
            end = mid - 1;
        }
    }
    cout << ret;
    return 0;
}

풀이

start, end, mid는 더하는 과정에서 int의 범위를 넘어갈 수 있기에 long long으로 선언해줘야 한다.
무엇이든 많이 풀어봐야 방법을 아는 것 같다.