[중급 알고리즘] 이분 탐색(연습)

💚 2343 기타 레슨

블루레이의 크기는 모두 같아야 한다.

i번과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다.

블루레이 크기 = 그룹에 속해있는 레슨의 합

블루레이 크기의 최소값을 구한다 = 그룹의 합의 최대값의 최소값 구하기

 

이분 탐색으로 찾아야 하는 값 : 블루레이의 크기

 

#include <iostream>
using namespace std;
int n, m;
int a[100000];
// 크기가 size인 블루레이로 녹화하여 M개 이하의 블루레이가 나오는가?
bool go (int size) {
    int cnt = 1;
    int sum = 0;
    for(int i = 0;i < n;i++) {
        // 다음 블루레이로
        if(sum + a[i] > size) {
            cnt += 1;
            sum = a[i];
        }
        else {
            sum += a[i];
        }
    }

    return cnt <= m;
}
int main() {
    cin >> n >> m;
    int left = 0;
    int right = 0;

    for(int i = 0;i < n;i++) {
        cin >> a[i];
        // 블루레이 최소 크기: 레슨 크기의 최대값
        // 블루레이 최대 크기: 레슨 크기의 합
        if(left < a[i]) {
            left = a[i];
        }
        right += a[i];
    }

    int ans = 0;
    while(left <= right) {
        int mid = (left + right) / 2;
        if (go(mid)) {
            ans = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }

    cout << ans << '\n';
}

💚 13397 구간 나누기 2

구간의 점수 = 구간에 속한 수의 최대값 - 최소값

여기서 여러 개의 구간을 어떻게 이분 탐색으로 나누지라는 고민이 든다.

하지만 구간의 점수에 대한 이분 탐색을 시도하면 가능하다.

구간의 점수가 곧 최대값과 최소값이므로, 둘의 차이가 가정해둔 구간의 점수보다 크면 현재 지점부터 다음 구간으로 설정하는 식으로 구간을 생성해나간다. 그렇게 파악한 구간의 수로 m보다 적은지 판단할 수 있다.

 

#include <iostream>
#include <vector>
using namespace std;

int go (vector<int> &a, int mid) {
    int n = a.size();
    int t1 = a[0];
    int t2 = a[0];
    int ans = 1;

    for(int i = 1;i < n;i++) {
        // 최대값
        if (t1 > a[i]) {
            t1 = a[i];
        }
        // 최소값
        if (t2 < a[i]) {
            t2 = a[i];
        }
        if (t2 - t1 > mid) {
            ans += 1;
            t1 = a[i];
            t2 = a[i];
        }
    }

    // cout << ans << endl;
    return ans;

}
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    int l = 0;
    int r = 0;

    for(int i = 0;i < n;i++) {
        cin >> a[i];
        if(r < a[i]) {
            r = a[i];
        }
    }

    int ans = r;
    // cout << ans << endl;
    while(l <= r) {
        // mid: 구간의 점수의 최댓값
        int mid = (l + r) / 2;
        if(go(a, mid) <= k) {
            r = mid - 1;
            // cout << r << endl;
            if(ans > mid) {
                // cout << mid << endl;
                ans = mid;
            }
        }
        else {
            l = mid + 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

💚1981 배열에서 이동

경로(방법)가 여러 개 나온다는 점이 앞선 문제와 가장 큰 차이점

최대값과 최소값의 차이는 최대 200이다. 모든 방법을 해보기에 크지 않은 차이다.

 

최소값과 차이값이 모두 미정인 상태에서 최소값 mn은 for문으로 임의로 정하고 차이값을 찾는다는 식으로 탐색을 이어나간다.

 

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <tuple>
using namespace std;
int n;
int a[100][100];
bool c[100][100];
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0,0};

bool inside(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}
// mn: 최솟값, mx: 최댓값
bool bfs(int mn, int mx) {
    if(mn > a[0][0] || mx < a[0][0]) {
        return false;
    }
    // 2차원 배열 초기화
    memset(c, false, sizeof(c));
    // BFS
    queue<pair<int,int>> q;
    q.push({0, 0});
    c[0][0] = true;
    while(!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();
        for(int k = 0;k < 4;k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(inside(nx, ny)) {
                if(c[nx][ny] == false) {
                    // 인자로 주어진 최소, 최대 범위 내의 값인 경우에만 처리
                    if(mn <= a[nx][ny] && a[nx][ny] <= mx) {
                        q.push({nx, ny});
                        c[nx][ny] = true;
                    }
                }
            }
        }
    }

    return c[n - 1][n - 1];
}

bool go(int diff) {
    // mn 최솟값
    for(int mn = 0;mn + diff <= 200;mn++) {
        if(bfs(mn, mn + diff)){
            return true;
        }
    }

    return false;
}
int main() {
    cin >> n;
    // 최소값은 for문, 차이는 이분 탐색으로 nested finding
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            cin >> a[i][j];
        }
    }

    int left = 0;
    int right = 200;
    int ans = 200;
    while(left <= right) {
        int mid = (left + right) / 2;
        if(go(mid)) {
            right = mid - 1;
            ans = min(ans, mid);
        }
        else {
            left = mid + 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

💚 1300 K 번째 수

해당 수보다 작은 수가 몇 개 있는지 파악하면 된다.

#include <iostream>
#include <algorithm>

using namespace std;


int main() {
    long long n, k;
    cin >> n >> k;
    long long left = 1;
    long long right = n * n;
    long long ans = 0;
    while(left <= right) {
        long long mid = (left + right) / 2;
        long long cnt = 0;
        for(long long i = 1;i <= n;i++) {
            cnt += min(n, mid / i);
        }

        if(cnt >= k) {
            ans = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

💚 1561 놀이 공원

쟁점: x분에 몇 번째 학생부터 몇 번째 학생이 놀이기구를 타는가

행은 놀이기구 종류고, 열은 분별로 탑승하는 학생의 숫자를 작성한 것이다.

예를 들어 8분까지 탑승한 학생의 수는

5 + 8 / 1 + 8 / 2 + 8 / 3 + 8/ 4 + 8 / 5 = 22

8분에 탑승한 학생의 수는 3명

(8 % 1 == 0, 8 % 2 == 0, 8 % 4 == 0)

#include <iostream>
#include <algorithm>

using namespace std;

int p, n;
int a[10000];
int main() {
    // p: 학생의 수, n: 놀이기구의 종류
    cin >> p >> n;
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }

    // 놀이기구의 종류 수가 학생의 수보다 더 많을 때
    if(p <= n) {
        cout << p << '\n';
        return 0;
    }

    long long left = 0;
    long long right = 2000000000LL * 1000000LL;
    while(left <= right) {
        // mid분에 타는 학생 번호: [begin, end]
        // 마지막 학생이 타는 시간을 알아내기 위함
        long long mid = (left + right) / 2;
        // 0분에 모든 학생 탑승 가능하므로 end는 n으로 초기화
        long long begin, end = n;
        for (int i = 0; i < n; i++) {
            end += mid / a[i];
        }

        begin = end;
        for(int i = 0;i < n;i++) {
            if(mid % a[i] == 0) {
                begin -= 1;
            }
        }
        begin += 1;

        if(p < begin) {
            right = mid - 1;
        }
        else if(p > end) {
            left = mid + 1;
        }
        else {
            for(int i = 0;i < n;i++) {
                if(mid % a[i] == 0) {
                    if(p == begin) {
                        cout << i + 1 << '\n';
                        return 0;
                    }
                    begin += 1;
                }
            }
        }
    }
    return 0;
}