[백준] 1654 - 랜선 자르기

1654. 랜선 자르기 풀이

난이도: Silver II
문제 주소: https://www.acmicpc.net/problem/1654

문제 풀이

이분 탐색을 활용하는 문제다주어지는 랜선의 길이는 최대 2^31 - 1로 굉장히 길고 필요한 개수 N도 1,000,000이나 되기 때문에 단순히 하나씩 길이를 조절하며 답을 찾는 건 시간 초과가 나기 때문에 이분탐색을 이용해야한다

1부터 가장 긴 랜선의 길이 사이에서 중간값인 mid를 정하고 그 길이로 잘랐을 때 나오는 랜선 개수가 N보다 크거나 같은지 확인하는 식이다. 만약 개수가 충분하다면 길이를 더 늘려서 최댓값을 찾아보고 부족하다면 길이를 줄여가며 범위를 좁히면 된다.

이분탐색 문제를 풀어본적이 있으면 굉장히 쉬운 문제인데 너무 오랜만에 이분탐색 구현하는거라 생각보다 푸는데 시간이 걸렸다

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <queue>
#include <string>
#include <unordered_map>

using namespace std;

long line[10001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    long n_max = 0;
    cin >> n >> k;
    for (int i = 0 ;i < n; i++) {
        cin >> line[i];
        n_max = max(n_max, line[i]);
    }

    long left = 1, right = n_max;
    long sol = 0;
    
    while (left <= right) {
        long mid = (left + right) / 2;
        long l = 0;
        
        for (int i = 0 ; i < n ; i++) l += line[i] / mid;

        if (l >= k) {
            sol = max(sol, mid);
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    cout << sol;
    return 0;
}

---

'Algorithm > 백준' 카테고리의 다른 글

[백준] 12865 - 평범한 배낭  (0)	2026.03.17
[백준] 11053 - 가장 긴 증가하는 부분 수열  (0)	2026.03.13
[백준] 10989 - 수 정렬하기 3  (0)	2026.03.08
백준 - 15829  (0)	2026.03.08
백준 - 2231  (0)	2026.03.07