[백준 C++] 1654 랜선 자르기 - 이분탐색

1654번: 랜선 자르기

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> Lines;

int main()
{
‌int K, N;
‌cin >> K >> N;

‌Lines.reserve(K);
‌for (int i = 0; i < K; ++i)
‌{
‌‌int Line;
‌‌cin >> Line;
‌‌Lines.emplace_back(Line);
‌}

‌int Result = 0;
‌long long Length = 0;
‌long long MinLength = 1;
‌long long MaxLength = *max_element(Lines.begin(), Lines.end());
‌while (MinLength <= MaxLength)
‌{
‌‌Length = (MinLength + MaxLength) / 2;

‌‌int Count = 0;
‌‌for (const int& Line : Lines)
‌‌{
‌‌‌Count += Line / Length;
‌‌}

‌‌if (Count < N)
‌‌{
‌‌‌MaxLength = Length - 1;
‌‌}
‌‌else
‌‌{
‌‌‌Result = Length;
‌‌‌MinLength = Length + 1;
‌‌}
‌}

‌cout << Result;
}

---

 

이전에 풀이한 2805(나무 자르기) 문제와 풀이방식이 거의 유사합니다.

 

이번 문제에서는 랜선의 길이가 INT_MAX값까지 가능하므로

길이 탐색을 위한 변수의 자료형 선택에 주의가 필요합니다.