(C/C++) 백준 1654번 - 랜선 자르기

문제 출처: https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

1. 코드

#include <iostream>
#include <algorithm>
using namespace std;
int k, n; // k = 영식이가 가짐, n = 필요한 랜선 개수
long long length[10001];
 
long long find(long long left, long long right) {
    //랜선의 길이를 최소가 1이고, 최대 Max로 설정해서 탐색시작
 
    while (left <= right) {
        int sum = 0;
        long long mid = (left + right) / 2; // 중간값
        for (int i = 0; i < k; i++) {
            sum += length[i] / mid; //sum은 랜선들을 mid로 나눈 몫들의 합
                                    //이걸 n과 비교해줘야함
        }
        if (sum >= n) {
            //찾은 갯수가 원하는 n보다 크면 더 큰 수로 나눠줘야함
            left = mid + 1;
        }
        else {
            //찾은 갯수가 n보다 작으면, 더 작은 수로 나눠줘야함
            right = mid - 1;
        }
    }
    return right;
}
int main() {
    long long Max = 0;
 
    scanf("%d %d", &k, &n);
    for (int i = 0; i < k; i++) {
        scanf("%lld", &length[i]);
        
        // 가지고 있는 랜선들 중 가장 긴 것을 Max로 설정
        Max = max(length[i], Max);
    }
    printf("%lld\n", find(1, Max));
    return 0;
}

 

2. 해결과정

이분 탐색 기법을 사용해주면 쉽게 풀수 있다.

처음에 left값을 1로, right값을 가지고 있는 랜선들 중 가장 긴 길이로 설정

mid값을 구해 이분 탐색 시작 -> 만들 수 있는 랜선들의 수를 구함

1) 만들 수 있는 랜선의 수(sum)이 요구되는 N개 보다 많거나 같으면 더 길이가 길게 나눠줘야 함 -> left = mid+1

- 랜선의 최댓값을 계속 업데이트 해줘야함

2) 만들 수 있는 랜선의 수(sum)이 요구되는 N개 보다 적으면 길이를 줄여준다 ->right = mid -1

 

3. 느낀점

처음에 long long 으로 입력을 받지 않고 int로 받았더니 출력이 계속 오류가 났던 문제였다.