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

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/2798

---

2. 풀이 과정

• 문제 해결의 흐름

1.  보통 1초의 제한은 약 1억회 연산을 수행할 수 있는 기준이며, N(카드의 개수)가 최대 100개이므로 3중 for문을 사용할 경우 최대 백만회의 연산을 수행하므로 주어진 시간 내에 해결 가능하다고 판단하였습니다.
2.  세 수의 합이 M을 초과하는 경우에는 break문을 사용하여 탐색을 중단하도록 효율을 높였습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    // 0. 입력 받기
    int N, M;  // N(3 <= N <= 100), M(10 <= M <= 300,000)
    cin >> N >> M;
    int num_lst[N];
    for (int i = 0; i < N; ++i) {
        cin >> num_lst[i];
    }

    // 1. 오름차순 정렬
    sort(num_lst, num_lst + N);

    // 2. 브루트포싱
    int result = 0;
    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 = num_lst[i] + num_lst[j] + num_lst[k];
                if (sum > M) break;
                result = max(result, sum);
            }
        }
    }

    // 3. 결과 출력
    cout << result << endl;

    return 0;
}

 

---

3. 후기

 항상 오름차순 정렬할 때는 algorithm 라이브러리의 sort 함수를 사용해왔는데 이 함수는 퀵 정렬 기반이었다!