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

Junu Kim·2025년 12월 23일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

63/89

[2798] 블랙잭

난이도: ★★☆☆☆ • solved on: 2025-12-23

문제 요약

문제 유형: 브루트포스, 조합
요구사항: N장의 카드 중 서로 다른 3장을 골라 합이 M을 넘지 않으면서 가장 큰 합을 출력해야 한다.

사용 개념

자료구조
- int[] : 카드 값 저장
알고리즘/기법
- 3중 반복문으로 조합 탐색 (i < j < k)
- 조건 갱신(최댓값 업데이트)
핵심 키워드
- 조합(combination)
- 완전탐색(brute force)

풀이 아이디어

문제 분해

카드 3장을 뽑는 모든 경우의 수를 확인한다.

합이 M 이하인 경우만 후보가 된다.

그 중 가장 큰 합을 total에 저장한다.
핵심 로직 흐름
total = 0
for i in [0..n-1]:
  for j in [i+1..n-1]:
    for k in [j+1..n-1]:
      sum = cards[i] + cards[j] + cards[k]
      if sum <= m and sum > total:
         total = sum
print(total)
예외 처리

i < j < k로 인덱스를 제한해 중복 선택/같은 카드 2번 선택을 방지한다.

문제 조건상 정답이 항상 존재하므로 total 초기값은 0으로 충분하다.

코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        int n =  Integer.parseInt(s[0]);
        int m =  Integer.parseInt(s[1]);

        String[] arr = sc.nextLine().split(" ");
        int[] cards = new int[n];
        for(int i = 0; i < n; i++){
            cards[i] = Integer.parseInt(arr[i]);
        }

        int total = 0;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                for(int k = j+1; k < n; k++){
                    int sum = cards[i] + cards[j] + cards[k];
                    if(total < sum && sum <= m){
                        total = sum;
                    }
                }
            }
        }
        System.out.println(total);
    }
}

시간·공간 복잡도

시간 복잡도: O(N³)
- 최대 N=100이면 약 161,700번 조합(=100C3)이라 충분히 가능
공간 복잡도: O(N)

어려웠던 점

처음에 Queue로 hand를 컨트롤하려 했지만, 순차 제거 방식이라 다양한 조합을 놓칠 수 있었다.
배열로 hand를 직접 관리하려다 보니, 조건을 손으로 모두 작성해야 할 것 같아 유연하지 않았다.
결국 핵심은 “3장을 고르는 모든 경우”이므로, 인덱싱(i<j<k) 으로 조합을 만드는 방식이 가장 깔끔했다.

배운 점 및 팁

“몇 개를 뽑아서 최적값” 문제는 우선 조합을 직접 만들 수 있는지(i<j<k) 를 먼저 떠올리는 게 빠르다.
sum을 변수로 빼두면 조건식이 깔끔해지고 중복 계산이 줄어든다.
입력은 BufferedReader + StringTokenizer로도 최적화 가능하지만, 이 문제는 Scanner로도 충분히 통과 가능하다.