백준 1654번 [랜선 자르기](C++)-yes6686- 티스토리

백준 문제 풀이: 1654 [랜선 자르기]

---

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

문제 설명:

길이가 각각 다른 K개의 랜선을 최소한 N개의 같은 길이로 잘라야 합니다. 만들 수 있는 최대 랜선의 길이를 구하는 문제입니다.

---

문제 해결 코드

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

long long int arr[10001];

int main() {
    int k, n;
    cin >> k >> n;

    int max = -1;
    for (int i = 0; i < k; i++) {
        cin >> arr[i];
        if (max < arr[i]) {
            max = arr[i];
        }
    }

    long long int start = 1;
    long long int end = max;
    long long int cnt = 0;
    long long int result = 0;
    long long int mid;

    while (start <= end) {
        mid = (start + end) / 2;
        cnt = 0;

        for (int i = 0; i < k; i++) {
            cnt += arr[i] / mid;
        }

        if (cnt < n) {
            end = mid - 1;
        } else {
            start = mid + 1;
            result = mid;
        }
    }

    cout << result << endl;
}

---

코드 설명

• 핵심 아이디어: 이분 탐색을 활용하여 가능한 랜선의 최대 길이를 효율적으로 탐색합니다.
• 구현 세부사항:
  • start: 이분 탐색의 시작 값 (최소 길이는 1).
  • end: 이분 탐색의 종료 값 (가장 긴 랜선의 길이).
  • mid: 현재 탐색 중인 랜선의 길이.
  • 각 길이로 자를 수 있는 랜선의 수를 계산하여 cnt에 저장하고, 조건에 따라 start와 end를 조정합니다.
• 시간 복잡도: O(k log(max_length))
  • 이분 탐색의 시간 복잡도는 O(log(max_length))입니다.
  • 각 반복에서 k개의 랜선을 확인하므로 O(k)입니다.

---

결과

주어진 조건에서 만들 수 있는 최대 랜선 길이를 출력합니다. 이분 탐색을 활용하여 효율적으로 문제를 해결했습니다.

다른 접근 방식이나 질문이 있다면 댓글로 남겨주세요!