백준 1654번 랜선 자르기 C++ 이분탐색

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

1654번: 랜선 자르기

 

문제 풀이

 이 문제는 이분 탐색을 사용하는 전형적인 문제이다. 랜선의 길이를 이용해서 이분 탐색을 하면 된다.

여기서 색칠된 영역의 길이들은 그 길이로 랜선들을 나누었을 때 개수가 충분한 길이이다.

 

 먼저, 왼쪽 포인터를 L, 오른쪽 포인터를 R라고 했을 때, 초기 값은 L=1,  R은 랜선의 길이 중 최대 길이로 지정한다. 이제 이 둘의 평균인 M을 보면 두 가지 경우가 있다.

1. M의 길이로 랜선들을 나누었을 때 가능한 최대 개수가 N미만인 경우(색칠된 영역에 존재하지 않는 경우)
2. M의 길이로 랜선들을 나누었을 때 가능한 최대 개수가 N이상인 경우(색칠된 영역에 존재하는 경우)

 먼저 1번 케이스의 경우 M이 더 짧아져야하므로 포인터 R을 M위치로 이동시킨다. 2번 케이스의 경우에는 M이 구하는 정답이 될 수도 있지만 조건을 만족시키면서 M보다 더 긴 길이가 존제할 수도 있으므로 L포인터를 M+1 위치로 이동시킨다. 여기서 M 위치가 아니라 M+1 위치로 이동시키는 이유는 나중에 처리하기 편해서이다.(M위치로 이동시키면 L과 R의 위치가 1차이가 날 때 반복문을 못 나올 수도 있음). M이 만약 최대 길이인 경우에는 L포인터는 조건을 최초로 만족시키지 않는 길이에 마지막까지 있을 것이다. 따라서 출력은 L-1을 해주면 된다.

 

 예외) 만약 4 4 1000 1000 1000 1000 과 같은 입력이 주어지면 위의 그림에서 1과 1000 사이, 모든 길이가 가능하게 되는데, 그러면 최종적으로 L=R=1000이 되므로 출력은 999가 된다. 따라서 이런 경우를 대비해 미리 R을 (최대길이)+1로 설정해두어야한다.

 

시행 착오

코드를 잘 짜고 백준에 제출했는데 50%정도에서 틀렸습니다 라고 나와서 자료형을 제대로 했는지 확인해보았다. 처음에는 나누어진 랜선의 개수가 정수형 범위를 넘을 수도 있을 거라고 생각해서 랜선의 개수를 long long으로 선언했었는데 여전히 틀리게 나왔다. 이후 게속 관찰하다가 R의 최대가 2^31 - 1인데 여기에 +1을 하면 int범위를 넘어가서 R을 long long으로 선언해주었다. 근데 그래도 똑같이 틀렸다. R = mx + 1로 정의해주었는데 mx가 int여서 R에 값이 저장될 때 오버플로우가 일어난 뒤에 long long으로 저장된 거였다. 그래서 mx도 long long으로 선언해주니 맞았다고 나왔다.

 

코드

#include <iostream>
using namespace std;

long long N,M,le[1000000],mx;
int main()
{
    cin>>N>>M;
    for(int i=0;i<N;i++)
    {
        cin>>le[i];
        if(mx < le[i])
        {
            mx = le[i];
        }
    }
        
    long long r = mx + 1, l = 0, mid;
    while(r>l)
    {
        long long num=0;
        mid = (l+r)/2;
        
        for(int i=0;i<N;i++)
        {
            num += le[i]/mid;
        }
        
        if(num>=M)
        {
            l = mid + 1;
        }
        else
        {
            r = mid;
        }
    }
    cout<<l-1;
}