[BOJ 2798] 블랙잭 - [브루트포스]

[BOJ 2798] 블랙잭 - [브루트포스]

문제 링크

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

문제 요약

$N$개의 카드 중에서 3장을 골라 합을 만들 때, 목표값 $M$을 넘지 않으면서 $M$에 가장 가까운 카드 3장의 합을 구하는 문제.

접근 방법

• 자료구조: std::vector<int> (입력받은 카드 숫자를 저장하기 위한 동적 배열)
• 알고리즘: 브루트포스 (완전 탐색)
• 핵심 아이디어: - 카드 개수 $N$이 최대 100개로 매우 적음.
  • 3장을 뽑는 조합($_NC_3$)의 경우의 수는 최대 161,700가지이므로, 3중 반복문을 통해 모든 경우를 다 계산해도 제한 시간(1초) 내에 충분히 해결 가능함.

풀이 코드

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

using namespace std;

int main() {
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<int> cards(N);
    for (int i = 0; i < N; i++) {
        cin >> cards[i];
    }

    int maxSum = 0;

    // 3장의 카드를 고르는 3중 반복문 (완전 탐색)
    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 currentSum = cards[i] + cards[j] + cards[k];

                // 합이 M 이하이면서 현재까지의 maxSum보다 크면 갱신
                if (currentSum <= M && currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
    }

    cout << maxSum << "\n";

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(N^3)$ - 3중 반복문을 사용하여 모든 조합을 탐색함. ($N=100$일 때 약 16만 번의 연산)
• 공간 복잡도: $O(N)$ - 카드 정보를 저장하는 배열 공간.

실행 결과

• 메모리: 2020 KB
• 시간: 0 ms

핵심 포인트

1. 인덱스 관리: 3중 반복문을 돌 때 동일한 카드를 중복 선택하지 않도록 각 반복문의 시작 인덱스를 이전 단계 인덱스 + 1로 설정함 (j = i + 1, k = j + 1).
2. 조건부 최댓값 갱신: 단순히 $M$에 가까운 값을 찾는 것이 아니라, $M$을 넘지 않아야 한다는 조건(currentSum <= M)을 반드시 체크해야 함.

예제 확인

• 예제 1: $N=5, M=21$ / 카드: $\{5, 6, 7, 8, 9\}$ -> $5+7+9 = 21$ 출력.
• 예제 2: $N=10, M=500$ / 카드: $\{93, 181, 245, 214, 315, 36, 185, 138, 216, 295\}$ -> $497$ 출력.