[C++] 백준 2798번 블랙잭

https://www.acmicpc.net/problem/2798

풀이

이 문제는 브루트포스 알고리즘을 적용하여 풀었다.
즉, 모든 경우를 다 탐색한 후 최대값을 출력하였다.

먼저 $N$개의 카드를 오름차순 정렬한 후 $M$보다 작은 수 중 최대값을 찾는다. ($M$보다 크거나 같은 수는 3개의 수를 더해서 M을 만드는 데 사용될 수 없기 때문)
이를 n3라고 하면, n3보다 작은 수 n2, n1을 순차적으로 탐색하면서 세 수의 합을 구한다. n3도 감소시키면서 모든 경우에서의 합을 구한다. 이때, 합이 $M$보다 작거나 같으면 정답 후보이다.
후보 중 가장 큰 수를 출력한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int>& card, int idx, int M) {
    int sum = 0, max = 0;
    
    for(int i=idx; i>=2; i--) {
        sum += card[i];
        for(int j=i-1; j>=1; j--) {
            sum += card[j];
            for(int k=j-1; k>=0; k--) {
                sum += card[k];
                if(sum <= M && sum > max) max = sum;
                
                sum -= card[k];
            }
            sum -= card[j];
        }
        sum -= card[i];
    }
    
    return max;
}

int main()
{
    int N, M;
    int idx = 0;
    const int INF = 300005;
    
    vector<int> card;
    
    cin >> N >> M;
    for(int i=0; i<N; i++) {
        int x;
        cin >> x;
        card.push_back(x);
    }
    
    sort(card.begin(), card.end());
    card.push_back(INF);
    
    idx = lower_bound(card.begin(), card.end(), M) - card.begin() - 1;

    cout << solution(card, idx, M);

    return 0;
}