[BaekJoon] 백준 2798 블랙잭 (Python / 파이썬)

BaekJoon 백준 BOJ 2798 블랙잭 문제는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. 고른 카드 3장의 합을 구하는 문제이다. 난이도는 Bronze 2이다.

 

BaekJoon 2798 블랙잭 문제 정보

출처

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

알고리즘 분류

- 브루트 포스 알고리즘 (brute force algorithm)

난이도

- 브론즈 2 / Bronze 2

 

블랙잭 문제 요약

• 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.
• 각 카드에는 양의 정수가 쓰여 있다. 그다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 
• 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
• N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구하여 출력한다.
• 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 카드에 쓰여 있는 수는 100,000을 넘지 않는 양의 정수이다.

 

문제 풀이 과정

1. N장의 카드 모두를 3개씩 골라서 합하여 보고 그 합이 M을 넘지 않으면서 M에 최대한 가까운 값을 찾아야 한다.
2. 카드를 뽑는 순서는 상관없다는 것을 생각하여 뽑을 1, 2, 3번째 카드에 대해 각각 중첩 반복문을 작성한다.
3. 카드 3 장의 조합을 모두 탐색하면서 합이 M을 넘지 않고 가장 큰 수를 구하여 출력한다.

 

코드 및 설명

N, M = map(int, input().split())
cardNum = list(map(int, input().split()))
ans = 0
for first in range(N - 2):
    for second in range(first + 1, N - 1):
        for third in range(second + 1, N):
            sum = cardNum[first] + cardNum[second] + cardNum[third]
            if sum <= M:
                ans = max(ans, sum)
print(ans)

---

BaekJoon 백준 BOJ 2798 블랙잭 문제를 파이썬 python으로 풀어보았다. 브루트 포스 알고리즘 활용 문제로 난이도는 Bronze 브론즈 2이다.