이분 탐색(백준 2512번과 2343번)

백준 2512번

백준 2343번

이분탐색은 수능 수학에서 몇몇 객관식 문제를 떠올리게 한다. 

제한된 시간내에서 빨리, 그리고 정확하게 풀기 위해서 보기 5개를 대입해서 풀 수 있는 문제들이 있었다. 엄밀하지는 않지만 답을 맞출 수 있는 방법. 

이분탐색은 엄밀하다. 컴퓨터의 훌륭한 연산능력을 이용해 답을 찾아가는 것이다. 

기존에 배운 알고리즘과는 다른 양상인데, 원래 배웠던 것들이 답을 찾아가는 것이라면 이건 오답을 걸러내 답만 남기는 방식이었다. 

이 글에서는 이분탐색 문제들을 풀면서 좀 헷갈리거나 실수했던 것들을 정리해본다. 

---

다음은 백준 2512번 풀이이다. 

//
//  main.cpp
//  2512
//
//  Created by CFox on 2020/03/02.
//  Copyright © 2020 CFox. All rights reserved.
//

#include <iostream>

int main(int argc, const char * argv[]) {
    int N;
    long long budget[10001];
    long long stand;
    long long lo = 1;
    long long hi = -1;
    
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%lld",budget+i);
        if(hi<budget[i]) hi = budget[i];
    }
    scanf("%lld",&stand);
    
 
    hi++;
    while(lo+1<hi){
        long long mid = (lo+hi)/2;
        long long sum = 0;
        
        for(int i=0;i<N;i++){
            if(budget[i]>mid) sum += mid;
            else sum += budget[i];
        }

        if(sum<=stand) lo = mid;
        else hi = mid;
        
       
    }
    printf("%lld",lo);
    
}

처음 풀 때, hi 를 무작정 엄청 큰 수로 할당해 풀었었다. 당연히 틀렸고. 이분탐색을 공부하면서 엄청 큰 수부터 반 씩 쪼개서 들어간다는 생각이 있어서 그런 식으로 풀었는데 결론부터 말하면 틀린 생각이었다. 

애초에 문제에서 준 시간이 넉넉해서 사실 큰 수나 작은 수나 큰 의미는 없을 것이라 생각해, 큰 수를 넣고 했는데 계속 틀려서 많은 생각을 한 결과 hi라는 변수의 값을 저렇게 받았다. 

 

위 문제의 경우, 왜 큰 값을 받으면 안되는지 살펴보자. 

배정된 예산의 상한값중 최솟값을 찾는 문제인데 

상한값이 클수록    -> 총 예산이 늘어남

상한값이 작을수록 -> 총 예산이 줄어듬 

자명하다. 하지만 상한값이 일정수준을 넘어버리면(제안된 예산들의 최댓값보다 커지면) 총예산의 값이 일정하다. (모든 예산을 다 더한 값으로)  

 

나의 풀이는 총예산의 값이 기준 총예산(예제에서는 485)보다 작거나 같으면 상한값을 높이기 위해 이분탐색으로 중간값을 lo라는 변수에 저장했는데 여기서 문제가 발생한다. 

적당한 값이 아닌 너무 큰 값을 hi로 잡게 되면 처음 mid의 값이 너무 커 총예산의 값이 모든 예산값들의 합인데, 예제처럼 주어지는 값(예제에서는 485)이 모든 예산값들의 합(예제에서는 520)보다 작으면 상관이 없지만 그 값과 같거나 크면 내 코드는 무지막지하게 큰 mid의 값을 lo 변수에 넣게 된다. (기준 총예산과 같은 값이 나오므로) 

예를 들어보자면 

4

4 3 2 1

10 

과 같은 경우이다. 당연히 10을 11이나 12와 같이 10보다 큰 수로 바꾸어도 결과는 틀리게 나온다. 

 

즉 답이 내가 정한 엄청 큰수에서 1을 뺀 수로 나오게 된다. (이분탐색으로 점점 hi값에 다가가니까)

 

따라서 이를 해결하려면 두 가지 방법이 있는데 

1. 밑에 조건문에서 저런 조건들을 추가해, 처음 들어오는 값들(제안된 예산들)의 합이 기준 총예산보다 크거나 같으면 걸러주는 것

2. hi의 값을 정상적인 범주로 줄이는 것 

 

나는 두 번째 방법이 더 간단할 것 같아 그 방법을 써서 풀었다. 

줄이는 법은 간단하다. 제일 큰 예산 제안값보다 1 크게 설정하면 된다.  

1을 더해주지 않을 경우, 나는 lo 값을 반환하게 코드를 짰는데

만약 문제가 모든 예산을 수용가능할 경우, 답은 제일 큰 예산안의 값이 나오게 된다. 이 경우 1을 더하지 않으면 hi의 값이 가장 큰 예산안이 되어 버리므로, 답에 접근을 할 수가 없어 hi-1의 값이 최종 lo 의 값, 즉 답이 된다. 

따라서 1을 더해준다. 이런 식으로 답안을 수정해서 겨우 통과했다. 

이분 탐색이라고 해서 끝점을 엄청 큰 수로 하는 것은 아니라는 것을 염두에 두자.

---

다음은 백준 2343번 풀이다. 

//
//  main.cpp
//  2343
//
//  Created by CFox on 2020/03/03.
//  Copyright © 2020 CFox. All rights reserved.
//

#include <iostream>

int main(int argc, const char * argv[]) {
    int lesson, blueray_num,blueray[100001];
    scanf("%d %d",&lesson,&blueray_num);
    long long hi = 0;
    for(int i=0;i<lesson;i++){
        scanf("%d",blueray+i);
        hi += blueray[i];
    }
    long long lo = 1;
    
    
    while(lo<hi){
        long long count = 0;
        long long mid = (lo+hi)/2;
        long long pre = mid;
        for(int i=0;i<lesson;i++){
            if(pre>=blueray[i]){
                pre -= blueray[i];
                if(i == lesson-1) count++;
                else if(pre<blueray[i+1]){
                    count++;
                    pre = mid;
                }
            }
            else {
                count = blueray_num+1;
                break;
            }
            
        }
        if(count <= blueray_num) hi = mid;
        else{
            lo = mid;
            if(lo+1 == hi) break;
        }
        
    }
    
    printf("%lld",hi);
    
}

이 문제는 처음 풀었을 때, 어디서 틀렸는지 몰라 참 난감했다. 

반례도 찾지 못해서 힘들었는데, 위 문제와 마찬가지로 하나의 유형에서 풀이가 틀리다는 것을 알아냈다. 

초기 코드는 아래와 같았다. 

 

//
//  main.cpp
//  2343
//
//  Created by CFox on 2020/03/03.
//  Copyright © 2020 CFox. All rights reserved.
//

#include <iostream>

int main(int argc, const char * argv[]) {
    int lesson, blueray_num,blueray[100001];
    scanf("%d %d",&lesson,&blueray_num);
    long long hi = 0;
    for(int i=0;i<lesson;i++){
        scanf("%d",blueray+i);
        hi += blueray[i];
    }
    long long lo = 1;
    
    
    while(lo+1<hi){
        long long count = 0;
        long long mid = (lo+hi)/2;
        long long pre = mid;
        for(int i=0;i<lesson;i++){
            if(pre>=blueray[i]){
                pre -= blueray[i];
                if(i == lesson-1) count++;
                else if(pre<blueray[i+1]){
                    count++;
                    pre = mid;
                }
            }
            else{
                count += blueray_num;
                count++;
            }
        }
        if(count <= blueray_num) hi = mid;
        else lo = mid;
    }
    
    printf("%lld",hi);
    
}

차이점은 아래 if문을 보면 else 구문일 때, 조건이 하나 추가된 것과 while 조건문이다. 

while 조건문 lo와 hi 변수 두 개를 다루면 조금 까다로운 것 같아 하나로 줄이기 위해 바꿨다. 

사실 큰 실수는 if문에서 else 구문에서 나왔다. 처음 코드는 다음과 같은 예제에서 엉뚱한 답을 내놓는다는 것을 알게 되었다. 

4 2 

1 1 1 1 

 

답은 1이다. 다만 위 내 잘못된 코드는 2를 뱉었다. 

처음에 문제를 보고 블루레이를 M개 만든다고 해서 딱 M개일 때 최솟값을 구하는 줄 알았는데, 개수는 M개보다 적어도 되는 것을 나중에 깨달았다. 이걸 알고도 처음에는 반례를 찾지 못했다. 따라서 그 조건을 빼주기 위해 if 문을 추가했다. 

마지막에 lo 와 hi 의 차이가 1인 경우 (예를 들면 여기서는 (1,2), 문제 예시에서는 내 코드 기준 (16,17)) 

둘 중 한 개는 답인데, 상황에 따라 어떤 것은 lo가 답이고, 어떤 것은 hi 답일 수 있다. 이를 표현하고자 저걸 추가했다. 

---

알고리즘 문제 푸는 건 재밌는데 막힐 때마다, 반례가 생각 안 나면 그것만큼 짜증나는 일도 없는 것 같다. 

이 글이 누군가에게 도움이 되길 바란다. 

위 코드에서 int로 적어도 되는 걸 long long으로 바꾼 이유는 코드가 안 돌아가는 이유가 혹시 저것인가 싶어 전부  바꿔봤다. (물론 int 문제인 경우는 틀렸습니다 가 나오지 않는다.)