C++로 T분을 넘지 않는 최대 문제 풀이 시간 구하기 – 미트 인 더 미들 기법

문제 개요

N개의 원소를 가진 배열 A와 숫자 T가 주어졌다고 가정해 봅시다. Amal은 프로그래밍 대회에 참가하려고 하는데, 대회는 총 T분 동안 진행되며 N개의 문제가 출제됩니다. i번째 문제를 푸는 데는 A[i]분이 걸립니다. 그는 N개의 문제 중 원하는 만큼(0개 이상) 골라서 풀되, 선택한 문제들을 푸는 데 걸리는 총 시간이 T분을 넘지 않도록 해야 합니다. 우리가 구해야 할 것은 그가 고른 문제들을 해결하는 데 걸릴 수 있는 가장 긴 시간입니다.

예를 들어 입력이 T = 17, A = [2, 3, 5, 7, 11]이라면 출력은 17이 됩니다. 앞의 네 문제를 선택하면 2 + 3 + 5 + 7 = 17분이 걸리는데, 이것이 제한 시간인 17분을 초과하지 않으면서 만들 수 있는 최대 시간이기 때문입니다.

풀이 접근: 미트 인 더 미들(Meet in the Middle)

가능한 모든 부분 집합을 전수 조사하면 시간 복잡도가 O(2^N)이 되어 N이 조금만 커져도 감당하기 어렵습니다. 대신 배열을 반으로 나누어 각각의 부분 집합 합을 먼저 구한 뒤, 한쪽을 정렬하고 이진 탐색으로 짝을 찾으면 연산량을 O(2^(N/2)) 수준으로 크게 줄일 수 있습니다.

단계별 과정

• 배열 A를 절반으로 나누어 b와 c 두 배열에 저장합니다.
• b의 모든 부분 집합 합을 계산해 배열 B에, c의 모든 부분 집합 합을 계산해 배열 C에 저장합니다.
• C를 오름차순으로 정렬합니다.
• B의 각 원소 B[i]에 대해 남은 시간 t − B[i]가 음수이면 해당 경우는 건너뜁니다.
• 그렇지 않으면 C에서 t − B[i]보다 큰 첫 번째 원소의 위치(upper_bound)를 찾은 뒤 한 칸 앞으로 이동하여, t − B[i] 이하인 값 중 최댓값 *itr을 얻습니다.
• *itr + B[i]가 지금까지의 최댓값 mx보다 크면 mx를 갱신합니다.
• 모든 탐색이 끝나면 mx를 반환합니다.

구현 예시

아래 C++ 코드를 보면 풀이 과정을 더 명확하게 이해할 수 있습니다.

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

int solve(int t, vector<int> A){
    int n = A.size();
    vector<int> b(n / 2), c(n - n / 2);
    for (int i = 0; i < n / 2; i++)
        b[i] = A[i];
    for (int i = n / 2; i < n; i++)
        c[i - n / 2] = A[i];
    vector<int> B, C;
    for (int bit = 0; bit < (1 << (n / 2)); bit++){
        int p = 0;
        for (int i = 0; i < n / 2; i++){
            if (bit & (1 << i))
                p += b[i];
        }
        B.push_back(p);
    }
    for (int bit = 0; bit < (1 << (n - n / 2)); bit++){
        int p = 0;
        for (int i = 0; i < n - n / 2; i++){
            if (bit & (1 << i))
                p += c[i];
        }
        C.push_back(p);
    }
    int mx = 0;
    sort(C.begin(), C.end());
    for (int i = 0; i < B.size(); i++){
        if (t - B[i] < 0)
            continue;
        auto itr = upper_bound(C.begin(), C.end(), t - B[i]);
        itr--;
        mx = max(mx, *itr + B[i]);
    }
    return mx;
}
int main(){
    int T = 17;
    vector<int> A = { 2, 3, 5, 7, 11 };
    cout << solve(T, A) << endl;
}

입력

17, { 2, 3, 5, 7, 11 }

출력

17