[백준/BOJ] 10816번 : 숫자 카드 2, 1654번 : 랜선 자르기, 2805번 : 나무 자르기 (이분 탐색)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 10816번 : '숫자 카드 2', 1654번 : '랜선 자르기', 2805번 : '나무 자르기' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Silver 티어에 해당하며, 문제를 풀이하기 위해 이분 탐색 알고리즘에 대한 이해가 필요합니다. (다만 일부 문제는 이분 탐색으로 분류되어 있음에도 더 쉽게 풀이할 수 있는 방법이 있다면 이분 탐색 알고리즘을 사용하지 않고 풀이한 것도 있습니다.)

 

 

10816번 : 숫자 카드 2

 

N개의 수가 주어지고 그 다음 M개의 수가 주어질 때 각각의 수가 몇 개 있었는지를 찾아서 출력하는 문제입니다.

정렬을 해준 뒤 그 수가 몇 개 있는지 찾아주면 되는데, N이 최대 50만이므로 이분 탐색 또는 log N 시간에 탐색할 수 있는 알고리즘을 사용하여 문제를 풀이해주어야 합니다.

 

다만 C++의 경우 algorithm 헤더 파일에 유용한 함수들이 많으므로 이들을 활용하여 쉽게 해결할 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> arr(N);
    for(int i=0; i<N; i++) cin >> arr[i];
    sort(arr.begin(), arr.end());

    int M; cin >> M;

    while(M--) {
        int val; cin >> val;
        cout << upper_bound(arr.begin(), arr.end(), val) - lower_bound(arr.begin(), arr.end(), val) << " ";
    }
}

 

upper_bound 함수와 lower_bound 함수를 이용하여 두 주소를 빼면 val 값에 해당하는 원소가 몇 개 있는지를 쉽게 구해줄 수 있으므로 이를 활용하여 위와 같이 간단하게 풀이할 수 있습니다.

 

 

 

 

1654번 : 랜선 자르기

 

K개의 랜선들을 적절히 잘라 N개의 랜선을 만들려고 할 때 각 랜선의 길이로 가능한 최댓값을 구하는 문제입니다.

이분 탐색으로 해결하는 것을 처음부터 떠올리기는 힘들지만, 문제 분류가 이분 탐색으로 되어있기 때문에 바로 이분 탐색으로 접근해보도록 하겠습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    long long K, N; cin >> K >> N;

    vector<long long> arr(K);
    long long Max = 0;
    for(int i=0; i<K; i++) {
        cin >> arr[i];
        Max = max(Max, arr[i]);
    }

    long long Left = 1, Right = Max, Mid, ans = 0;
    while(Left <= Right) {
        Mid = (Left + Right)/2;

        long long cnt = 0;
        for(int i=0; i<K; i++) cnt += arr[i]/Mid;

        if(cnt >= N) {
            Left = Mid + 1;
            ans = max(ans, Mid);
        }
        else Right = Mid - 1;
    }
    cout << ans;
}

 

주어진 K개의 길이를 가지고 최대 랜선의 길이를 한 번에 구하는 방법은 찾기 힘들어 보입니다.

따라서 1 ~ (모든 랜선 중 최대 길이) 사이의 정수 하나가 답이 될 것이므로 이 구간에서 이분 탐색을 사용하여 문제를 풀이할 수 있습니다.

 

N <= 1,000,000이므로 log N 시간에 충분히 해결이 가능합니다.

적절히 Mid를 잡고 범위 안에서 해당 Mid를 단위 길이로 했을 때 몇 개의 랜선이 나오는지를 기록하여 최대 랜선의 수를 가지는 Mid 값을 찾고, 그 때의 Mid를 출력해주면 됩니다.

 

그리고 int형으로 변수들을 두면 Mid = (Left + Right)/2를 계산하는 과정에서 Left + Right에서 오버플로우가 발생하므로 웬만하면 모든 자료형을 long long과 같이 여유있게 잡아주는 것이 좋습니다.

 

 

 

개인적으로 이 문제는 int형의 overflow를 모두 고려하여 문제를 푼다면 상당히 어려울 수 있으므로 Silver III보다는 조금 더 높게 난이도를 쳐줘도 되지 않나 싶습니다.

 

 

2805번 : 나무 자르기

 

문제 자체는 위의 랜선 문제와 거의 비슷하며, 접근 방식도 똑같이 하면 풀릴 것으로 보이는 문제입니다.

N개의 나무 길이 중 최댓값을 찾은 뒤 1 ~ 최댓값 사이에서 이분 탐색으로 적어도 M미터의 나무를 가져가기 위해 설정할 수 있는 최대 높이를 찾아주면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    long long N, M; cin >> N >> M;

    vector<long long> arr(N);
    for(int i=0; i<N; i++) cin >> arr[i];
    sort(arr.begin(), arr.end(), greater<int>());

    long long Left = 1, Right = arr[0], ans = 0;
    while(Left <= Right) {
        long long Mid = (Left + Right)/2;

        long long sum = 0;
        for(int i=0; i<N && arr[i]>Mid; i++) sum += arr[i] - Mid;

        if(sum < M) Right = Mid - 1;
        else {
            ans = Mid;
            Left = Mid + 1;
        }
    }
    cout << ans;
}

 

위의 문제와 풀이 코드도 거의 비슷하며, 다른 점이 있다면 vector를 sort 해준 뒤 나무 길이가 절단 길이보다 높아 절단하고도 나무가 남을 수 있는 것들에 한해서만 연산을 해주도록 코드를 작성해야 깔끔하다는 것입니다.

 

그 과정에서 내림차순으로 정렬하기 위해 sort 함수에서 greater<int>()를 사용해주며, 아래의 반복문에서도 arr[i] > Mid라는 조건을 추가해주어 탐색 시간을 최소화해주도록 합니다.