이분탐색(백준 6236번, 1654번, 2110번)

6236번

1654번

2110번

지난 이분탐색에 이은 연습용 쉬운 문제들이다. 

2110번만 아이디어 측면에서 어려움을 겪었다. 

정렬한 뒤, 무조건 첫번째 집부터 설치해야된다는 걸 알면 쉬울 듯하다. 

각각의 문제들에 대한 풀이다. 

 

---

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

#include <iostream>

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

지난번에 푼 문제와 유사하므로 풀이는 생략한다. 

---

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

#include <iostream>

int main(int argc, const char * argv[]) {
    int N,num;
    int lenson[1000001];
    scanf("%d %d",&N,&num);
    long long hi = 0;
    for(int i=0;i<N;i++){
        scanf("%d",lenson+i);
        hi += lenson[i];
    }
    long long lo = 1;
    hi++;
    
    while(lo+1<hi){
        long long mid = (lo+hi)/2;
        long long count = 0;
        for(int i=0;i<N;i++){
            count += lenson[i]/mid;
        }
        if(count<num) hi = mid;
        else lo = mid;
    }
    
    printf("%lld",lo);
    
}

오답율이 높은데 한 번에 맞춰서 좀 놀랬던 문제이다. 아마 int 자료형에서 실수가 나지 않았을까 싶다. 

코드를 보게 되면 굳이 long long 자료형을 이용한 것이 보인다. 

주어진 랜선의 길이는 int에 담겨도 원하는 값을 꺼내면서 이용하는 변수인 hi는 int자료형이 커버할 수 있는 크기보다 더 커질 수 있음을 유의하자. 

---

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

#include <iostream>
#include <algorithm>
int main(int argc, const char * argv[]) {
    using namespace std;
    int home, wifi;
    scanf("%d %d",&home,&wifi);
    int loc[200001];
    for(int i=0;i<home;i++){
        scanf("%d",loc+i);
    }
    sort(loc,loc+home);
    int lo = 0;
    int hi = loc[home-1] - loc[0]+1;
    
    while(lo+1<hi){
        int count = 1;
        int mid = (lo+hi)/2;
        int start = 0;
        for(int i=1;i<home;i++){
            if(loc[i] - loc[start] >= mid){
                count++;
                start = i;
            }
        }
        if(count>=wifi) lo = mid;
        else hi = mid;
    }
    printf("%d",lo);
    
    
}

어떻게 풀어야 하는지 감만 잡으면 코드 짜는건 어렵지 않다고 생각한다. 

---

이분탐색 연습용으로 좋은 세 문제를 가져왔다.