[백준]2798번. 블랙잭

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

 

 

3장의 카드를 조합했을 때 M을 넘지 않으면서 M에 최대한 가까운 카드의 합을 출력해줘야한다. N이 100까지로 크지 ㅇ낳아 3중 반복문으로 조합을 구현해도 시간복잡도가 괜찮을 것 같아서 M보다 작은 합중에 제일 큰 합을 구한 다음 출력해주었다.

 

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> cards(n);
    for (int i = 0; i < n; i++) {
        cin >> cards[i];
    }
    
    int max_sum = 0;  // M을 넘지 않으면서 가장 가까운 합을 저장
    
    // 세 장의 카드를 고르는 모든 경우를 탐색
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                int sum = cards[i] + cards[j] + cards[k];
                
                // 합이 M을 넘지 않는지 확인하고, M과 가장 가까운 합을 저장
                if (sum <= m && sum > max_sum) {
                    max_sum = sum;
                }
            }
        }
    }
    
    cout << max_sum << endl;
    return 0;
}