[SWEA] 3813 그래도 수명이 절반이 되어서는… (C++, 라이브러리 X)

August 10, 2021

Algorithm 카테고리의 다른 글

👉 [SWEA] 4038. 단어가 등장하는 횟수 (C++, 라이브러리 X) 2021-08-10

👉 [SWEA] 2948 문자열 교집합 (C++, 라이브러리 X) 2021-08-10

👈 [SWEA] 3813 그래도 수명이 절반이 되어서는… (C++, 라이브러리 X) 2021-08-10

👉 [SWEA] 3814 평등주의 (C++, 라이브러리 X) 2021-08-10

👉 [SWEA] 4753 호둥이의 단어찾기 (C++, 라이브러리 X) 2021-08-08

Divide-and-conquer(분할정복) 실전문제

풀이

최대값이 최소가 되도록 하는 문제는 대부분 Binary Search(이분탐색)으로 풀 수 있다.

코드 GitHub

#include <iostream>
using namespace std;

#define MAXN 200000

int W[MAXN], S[MAXN];
int N, K;

bool Verify(int val) {
    int pivot = -1;
    for(int k = 0; k < K; k++) {
        for(int s = 0; s < S[k]; s++) {
            pivot++;
            if(pivot == N) return false;
            if(W[pivot] > val) {
                k--;
                break;
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    for(int tc = 1; tc <= T; tc++) {
        cin >> N >> K;
        for(int n = 0; n < N; n++) cin >> W[n];
        for(int k = 0; k < K; k++) cin >> S[k];

        int l = 0, r = 200000;
        while(l < r) {
            int m = (l + r) / 2;
            if(Verify(m)) r = m;
            else l = m + 1;
        }
        cout << '#' << tc << ' ' << r << '\n';
    }
    return 0;
}