BOJ No.2798 [블랙잭]

Baekjoon Online Judge No.2798 [블랙잭]

---

   Code   

#include <iostream>
#include <vector>
 
using namespace std;
 
int N, M;
vector<int> cards;
 
int main() {
    cin >> N >> M;
    cards.resize(N);
 
    for (int i = 0; i < N; i++)
        cin >> cards[i];
 
    int answer = 0;
 
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            for (int k = j + 1; k < N; k++)
                if (cards[i] + cards[j] + cards[k] <= M)
                    answer = max(answer, cards[i] + cards[j] + cards[k]);
 
    cout << answer;
}

---

   How to solve   

  Brute force 로 풀어도 최대 O(100^3)의 시간복잡도밖에 가지지 않는다. #18 ~ #22 line 에서 3개를 고를 수 있는 모든 경우의 수를 다 따지면서, 뽑은 세 장의 카드의 합이 M 이하일 때(#21 line) #22 line 에서 answer 의 값을 재설정한다.