백준 2798 블랙잭 파이썬, C++

🎯 파이썬 알고리즘 문제풀이: 블랙잭 (완전탐색 3중 for문)

✅ 문제 설명

백준 2798번 문제는 N장의 카드 중 3장을 선택해 그 합이 M을 넘지 않으면서 가장 큰 값을 구하는 문제입니다.

• 총 N장의 카드가 주어집니다.
• 목표 숫자 M도 함께 주어집니다.
• 3장의 카드를 선택해 만든 합이 M을 넘지 않아야 합니다.
• 가능한 조합 중 M에 가장 가까운 값이 정답입니다.

예시 입력:

5 21
5 6 7 8 9

출력:

21

---

🔍 문제 접근 전략

🔹 정렬로는 부족합니다

처음에는 큰 수부터 더해가는 방식으로 접근할 수 있지만, 이는 **합이 M을 넘지 않아야 한다**는 조건에서 실패할 수 있습니다.
예:

9 + 8 + 7 = 24 > 21 → 불가능

🔹 완전탐색 필요

모든 3장 조합을 탐색해야 합니다. 수학적으로는 \(\binom{N}{3}\) 가지가 존재하며, N이 최대 100이라면 약 161,700개의 경우의 수로 시간 안에 해결 가능합니다.

🔹 구현 방식은 3중 for문

조건: i < j < k를 만족하는 세 개의 인덱스를 중첩 for문으로 구성합니다.

---

📄 전체 코드

# 입력 받기
N, M = map(int, input().split())
arr = list(map(int, input().split()))

best_sum = 0

# 완전탐색
for i in range(0, N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            current_sum = arr[i] + arr[j] + arr[k]
            if current_sum <= M and current_sum > best_sum:
                best_sum = current_sum

print(best_sum)

---

📌 코드 설명

코드	설명
N, M = map(int, input().split())	카드 개수와 목표값 입력 받기
arr = list(map(int, input().split()))	카드 숫자 배열로 저장
3중 for문	서로 다른 세 장의 카드 선택
if current_sum ≤ M and current_sum > best_sum:	조건 만족 시 최댓값 갱신

---

💡 코드 개선 아이디어

• sum, max 변수 사용 지양: 내장 함수와 충돌 방지
• 조기 탈출: 합이 M보다 크면 건너뛰기
• itertools.combinations 사용: 코드 간결화

from itertools import combinations

N, M = map(int, input().split())
arr = list(map(int, input().split()))

best_sum = 0
for comb in combinations(arr, 3):
    s = sum(comb)
    if s <= M and s > best_sum:
        best_sum = s

print(best_sum)

---

🧾 핵심 요약

항목	내용
알고리즘 분류	브루트포스 (완전탐색)
시간복잡도	\(O(N^3)\) (최대 100 → 약 161,700)
중요한 점	정렬만으로는 불가능. 조합을 모두 탐색해야 함

---

아래는 C++ 코드

#include <iostream>

using namespace std;

int main(void)
{
	int N, M,max=0,sum=0;
	cin >> N >> M;
	int* arr = new int[N];
	for (int i = 0; i < N; i++)
		cin >> arr[i]; 
	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++)
			{
				sum = arr[i] + arr[j] + arr[k];
				if (sum <= M)
				{
					if (max < sum)
						max = sum;
				}
			}
		}
	}
	cout << max << endl;

	delete[] arr;

}

📚 마무리

이 문제는 효율성보다는 완전한 탐색, 즉 조합을 놓치지 않고 모두 시도하는 연습에 적합한 문제입니다. 문제를 조건대로 정직하게 구현하는 것이 정답으로 가는 가장 빠른 길이 될 수 있습니다.

---