백준(BOJ) 1654 랜선 자르기 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

문제 풀이에 이용된 알고리즘: 이분 탐색

 

주어진 서로 다른 길이의 k개의 랜선을 똑같은 길이로 토막을 내어서, 동일한 길이의 랜선 n개를 만드는 가장 긴 랜선 토막의 길이를 찾는 문제이다.

 

랜선 토막의 길이를 1부터 1씩 증가시켜 나가면, 조건을 만족하는 가장 긴 토막의 길이를 구하는 것은 굉장히 단순하지만 확실한 방법이라는 것은 모두가 알 것이다.

 

하지만 누가봐도 비효율적인 방법이며, 이런 탐색을 조금 더 효율적으로 하기 위해서 이분 탐색으로 풀이를 진행하였다.

 

토막의 길이가 0일 수는 없으므로 left는 1로 초기화하고, right는 현재 주어진 랜선 중 가장 긴 것의 길이로 초기화한다.

 

이후부터는 이분 탐색을 통해 토막의 길이를 변화시키며, 해당 토막의 길이로 랜선들을 잘랐을 때 몇개의 토막을 얻을 수 있는 지 체크하는 방식으로 루프를 돌게 된다.

 

파이썬이라면 상관 없겠지만 C++ 사용자라면 이 문제에서 고려해야될 점이 하나 있다. mid를 구하기 위해서 left와 right를 더하고 2로 나누어야하는데, 이 때 int 형을 사용하면 오버플로우가 발생할 수 있다.

 

따라서 이런 상황을 모면하기 위해서 left, right, mid를 모두 long long 타입으로 선언해주었다.

 

/* BOJ 1654 랜선 자르기 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int k, n, arr[10001];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> k >> n;
    for (int i = 1; i <= k; i++)
        cin >> arr[i];
 
    ll left = 1, right = *max_element(arr + 1, arr + 1 + k);
    int ans = 0;
 
    while (left <= right)
    {
        ll mid = (left + right) / 2;
 
        int cnt = 0;
        for (int i = 1; i <= k; i++)
            cnt += (arr[i] / mid);
 
        if (cnt < n) // 조금더 잘게 잘라야함
            right = mid - 1;
        else ans = mid, left = mid + 1; // 조금 더 길게 잘라봐도 무방함
    }
 
    cout << ans << endl;
 
    return 0;
}