백준 2798번 [블랙잭](C++)-yes6686- 티스토리

백준 문제 풀이: 2798 [블랙잭]

---

문제 링크: https://www.acmicpc.net/problem/2798

문제 설명:

카드의 숫자가 주어질 때, 세 개의 카드를 선택하여 합이 주어진 숫자 m을 넘지 않는 가장 큰 값을 찾는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[101];
int dp[101];

int main() {
    int n, m;
    cin >> n >> m; // 카드 개수 n과 목표 값 m 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i]; // 카드 숫자 입력
    }

    for (int i = 2; i < n; i++) {
        for (int j = 1; j <= i - 1; j++) {
            for (int t = 1; t <= i - j; t++) {
                if (arr[i - j] + arr[i - j - t] + arr[i] <= m)
                    dp[i] = max(arr[i - j] + arr[i - j - t] + arr[i], dp[i]);
            }
        }
    }

    int max1 = -1;
    for (int i = 2; i < n; i++) {
        if (max1 < dp[i]) {
            max1 = dp[i];
        }
    }
    cout << max1 << endl; // 결과 출력
}

---

코드 설명

• 핵심 알고리즘: 완전 탐색을 사용하여 세 개의 카드 조합 중 합이 m을 넘지 않는 최대값을 찾음
• 구현 세부사항:
  • 중첩 루프를 사용하여 세 개의 카드의 합을 계산
  • 조건을 만족하는 합 중 최대값을 저장
• 시간 복잡도: O(n³)
  • 세 개의 카드를 선택하는 모든 경우의 수를 탐색

---

결과

카드 세 장의 합 중에서 m을 넘지 않는 가장 큰 값을 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!