백준 문제풀이 : (1654) 랜선 자르기 - C/C++

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

1654번: 랜선 자르기

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	128 MB	Silver 2	이분 탐색

 

 

문제

 

 

풀이

문제의 내용을 요약하자면, 주어진 K개의 랜선을 잘라 N개 이상의 (동일한 길이의) 랜선을 만들어야 하는데, 그 때 만든 랜선의 길이가 가장 긴 경우의 길이를 구하는 문제이다. 

 

예제의 경우 길이가 차례대로 802, 743, 457, 539 인 네 개의 랜선이 주어졌으며, 이 네 개의 랜선을 잘라 11개의 동일한 랜선을 만들어야 한다. 문제를 여기까지 이해했을 때 정리할 수 있는 내용은 다음과 같다.

 

1. 만든 랜선의 최대 길이는 주어진 랜선 중에서 가장 긴 랜선의 길이를 넘지 못한다.

2. 만든 랜선이 11개 이상인 경우의 수 중에서 만든 랜선의 길이가 가장 긴 경우를 찾아내야 한다.

 

따라서, 주어진 랜선 중 가장 긴 길이를 시작으로 만든 랜선의 길이를 탐색해나가고자 한다.

위 예제에서 가장 긴 길이의 랜선 길이는 802이다. 따라서 시작 길이를 802로 잡는다.

 

하지만 802 길이로 만들 수 있는 랜선의 수는 겨우 1개 이므로, 랜선의 길이를 줄여야 한다. 802를 2로 나누면 그만큼 만든 랜선의 길이는 늘어나지만, 길이는 줄어들게 된다. 만든 랜선의 개수와 만든 랜선의 길이는 반비례 관계에 있는 것이다.

 

이 점을 활용해 랜선 길이에 따른 랜선 개수를 비교해가며 정답을 탐색해나가보기로 한다. 어떤 기준 값이 주어져있고, 그 기준 값과의 비교를 통해 원하는 값을 탐색해나갈 때는 이분 탐색 알고리즘이 주로 사용된다. 이 문제에서도 이분 탐색을 통해 정답을 찾아낼 수 있다. 

 

예제를 통해 문제 풀이를 계속 따라가보자. 802를 반으로 잘랐으니, 현재 길이는 401이다. 401 길이로 랜선을 자르면 802에서 2개, 743에서 1개, 457에서 1개, 539에서 1개로 총 5개 랜선을 만들 수 있다. 만들어야 하는 랜선 개수 11개보다 적은 개수이다. 따라서 랜선의 수를 늘리는 방향으로 숫자를 조정해줘야한다. 랜선의 수를 늘리는 방향은 랜선의 길이를 줄이는 것이므로, 401을 다시한번 반으로 나눠준다. 단, 소수점은 취급하지 않으므로 나머지는 버린다.

 

위 과정을 거친 후 현재 랜선의 길이는 200이다. 길이 200으로 랜선을 자를 경우 만든 랜선의 개수는 11개이므로, 조건을 만족했다. 하지만 문제에서 원하는 답은 11개를 만족했을 때의 랜선 길이가 아니라, 11개 이상일 때의 경우들 중 랜선 길이가 가장 클 때의 길이이다. 

 

따라서, 만든 랜선의 길이가 11 이상인 상태이니, 이번에는 다시한번 랜선의 길이를 늘려서 검사를 진행해본다. 401일 때는 랜선 수가 모잘랐고, 200일 때는 랜선 수가 11개 이상이었다. 따라서 200과 401의 중간 값으로 검사를 진행한다. 

 

200과 401의 중간 값인 현재 값은 300이다. 길이 300으로 랜선을 잘라보면 만든 랜선의 총 개수는 6개로 11개 미만이다. 따라서 이번에는 길이를 축소해줘야하는데, 200일 때는 랜선수가 11개 이상이었고, 300일 때는 랜선 수가 11개 미만이었으니 그 중간 값으로 검사를 진행해본다. 

 

이런 식의 계산 및 검사를 계속 반복하다보면은 결국 범위가 점점 좁아져 한 지점에 이르게 된다. 그 지점이 바로 정답이고, 계속해서 중간값을 계산해나가는 패턴이므로 이분 탐색을 이용할 수 있다.

 

 

코드 작성

#include <iostream>
#include <math.h>

using namespace std;
long long num[10000];
//주어지는 랜선 길이의 최대값이 '2의 31승-1' 이므로 계산 중 int 범위를 벗어날 수 있다.
//long long 타입으로 선언해준다. 

int main() {
    int K, N;
    scanf("%d %d", &K, &N);
    
    long long max=0, min=0;
    for (int k=0 ; k<K ; k++) {
        scanf("%lld", &num[k]);
        if (num[k]>max) max = num[k];
        // 랜선 길이를 입력받는 과정에서 최대값을 구해둔다.
    }
    
    long long half = max; 
    //half에는 검사값(중간값)을 계산해서 넣는다. 
    //단, max 값도 정답이 될 수 있으니 첫 검사값은 max로 시작한다.
    while(true) {
        long long count=0;
        for (int k=0 ; k<K ; k++) {
            count+=num[k]/half;
        } //주어진 각 랜선을 검사값으로 잘랐을 때 몇 개가 나오는지 계산해 저장
        
        if (count<N) max = half; 
        //랜선의 개수가 모자르다면 길이를 줄여야 하므로 max를 최대값으로 변경 
        else min = half;
        //랜선의 개수가 딱 맞거나 그 이상이라면 길이를 늘려 검사해야하므로 최소값으로 변경
        
        if (half==(min+max)/2) break; //중간값 변화가 없는 상태라면 반복 종료
        
        half = (min+max)/2; //중간값을 구해서 저장
    }
    
    printf("%lld", half);
    
    
}

 

 

END.