백준 2798번: 블랙잭
카지노의 블랙잭 게임 규칙을 단순화한 문제입니다. 주어진 N장의 카드 중에서 3장을 뽑아, 그 합이 M을 넘지 않으면서 M에 가장 가까운 값을 찾아야 합니다. 모든 가능한 조합을 탐색하는 브루트포스(Brute-force) 알고리즘을 사용하여 해결하는 것이 핵심입니다.
✅ 문제 개요
| 항목 | 내용 |
|---|---|
| 문제 번호 | 2798번 - 블랙잭 |
| 난이도 | 브론즈 2 |
| 핵심 알고리즘 | 브루트포스(완전탐색) |
✅ 문제 설명 요약
- 입력:
- 첫째 줄: 카드의 개수
N(3 ≤ N ≤ 100)과 목표 합M(10 ≤ M ≤ 300,000) - 둘째 줄:
N개의 카드에 쓰여 있는 수 (100,000 이하의 양의 정수)
- 첫째 줄: 카드의 개수
- 출력: 주어진
N개의 카드 중 3장을 골라, 그 합이M을 넘지 않으면서M에 가장 가까운 합을 출력 - 규칙:
- 딜러는
N장의 카드를 모두 보여주고, 플레이어는 이 중 3장을 고릅니다. - 고른 3장의 카드의 합이
M이하여야 합니다. - 여러 조합이
M이하일 경우, 그 중 가장 큰 합을 선택합니다.
- 딜러는
✅ 풀이 전략
이 문제는 카드의 개수 N이 최대 100으로 크지 않기 때문에, 가능한 모든 3장 조합을 직접 다 확인해보는 브루트포스(Brute-force) 방식으로 해결할 수 있습니다.
1️⃣ 모든 3장 조합 만들기
- N장의 카드 중에서 순서에 상관없이 3장을 뽑는 모든 경우의 수를 확인해야 합니다. 이를 위해 3중
for반복문을 사용합니다. - 중요: 같은 카드를 여러 번 뽑으면 안 되므로, 각 반복문의 시작점을 이전 반복문 바로 다음 인덱스로 설정해야 합니다.
- 첫 번째 카드
i는0부터N-2까지 순회합니다. - 두 번째 카드
j는i+1부터N-1까지 순회합니다. - 세 번째 카드
k는j+1부터N까지 순회합니다.
- 첫 번째 카드
- 이 논리를 코드로 구현하면 다음과 같습니다.
// 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++) {
// cards[i], cards[j], cards[k]가 하나의 조합이 됨
}
}
}2️⃣ 조건 확인 및 최댓값 갱신
- 3중 반복문 안에서, 뽑은 3장의 카드의 합
sum을 계산합니다. - M에 가장 가까우면서도 M을 넘지 않는 최적의 합
result를 찾기 위해, 다음 두 가지 조건을 확인합니다.sum <= M: 합이 목표치 M을 넘지 않는가?sum > result: 현재까지 찾은 최적의 합result보다 더 큰가? (즉, M에 더 가까운가?)
- 두 조건을 모두 만족하면,
result값을 현재sum으로 갱신합니다.result는 처음에 0으로 초기화합니다.
예시: N=5, M=21, 카드 = [5, 6, 7, 8, 9]
1. 초기값: result = 0
2. 조합 (5, 6, 7) -> sum = 18. 18 <= 21이고 18 > 0이므로 result = 18.
3. 조합 (5, 6, 8) -> sum = 19. 19 <= 21이고 19 > 18이므로 result = 19.
4. ...
5. 조합 (6, 7, 8) -> sum = 21. 21 <= 21이고 21 > 19이므로 result = 21.
6. 이후 모든 조합을 확인해도 21보다 크거나, 21보다 작으면서 result보다 큰 경우는 없음.
7. 최종 result는 21이 됩니다.
✅ Java 코드 예제
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] cards = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
cards[i] = Integer.parseInt(st.nextToken());
}
int result = 0;
// 1. 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 sum = cards[i] + cards[j] + cards[k];
// 2. 조건 확인
// M을 넘지 않으면서, 이전에 찾은 최적의 합(result)보다 크면 갱신
if (sum <= M && sum > result) {
result = sum;
}
}
}
}
bw.write(String.valueOf(result));
bw.flush();
bw.close();
br.close();
}
}⚠️ 실전 주의사항
| 항목 | 설명 |
|---|---|
| 중복 방지 | 3중 반복문의 시작점을 i+1, j+1로 설정하여 같은 카드를 중복해서 선택하지 않도록 하는 것이 매우 중요합니다. |
| 시간 복잡도 | 3중 반복문을 사용하므로 시간 복잡도는 O(N³)입니다. N이 100일 때 약 1,000,000번의 연산으로 시간 제한(1초) 내에 충분히 통과 가능합니다. |
| 최적해 찾기 | result 변수를 두고, M을 넘지 않는 합 중에서 result보다 큰 값이 나타날 때마다 갱신하는 방식으로 M에 가장 가까운 최적해를 찾습니다. |
| 입력 처리 | 카드 목록은 두 번째 줄에 공백으로 구분되어 한 번에 들어오므로 StringTokenizer로 처리해야 합니다. |
📝 마무리 요약
✔️ 브루트포스(완전탐색)는 가능한 모든 경우의 수를 다 해보는 가장 간단하고 확실한 방법입니다.
✔️ 3중 for 반복문을 사용하여 N개 중 3개를 뽑는 모든 조합을 만듭니다.
✔️ 각 조합의 합이 M을 넘지 않으면서 이전에 찾은 최댓값보다 큰지 확인하여 답을 갱신합니다.
✔️ 데이터의 크기(N)가 작을 때 브루트포스는 매우 효과적인 해결책이 될 수 있습니다.
