[백준/파이썬] 2798: 블랙잭

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

 

문제 요약 : N장의 카드 중에서 3장의 카드를 골라 그 합이 M을 넘지 않으면서 최대한 M과 가깝게 만들어라

 

 

예제 입력1 :

5 21
5 6 7 8 9

 

예제 출력 1:

21

 

📌 풀이 )

 

 

3중 반복문을 사용하여 조합을 탐색하였다.

인덱스가 겹치지 않도록 i,j,k는 순서대로 증가한다. 이 조합으로 합이 M을 넘지않으면, max_sum에 넣어준다. 이때, 그전에 들어간 값과 비교하여 그 전값보다 클 경우에만 max_sum이 갱신된다.

 

3중 반복문을 사용하지만, 카드수 N이 작기 때문에(100이하) 풀 수 있는 문제이다.

def blackjack(N, M, cards):
    max_sum = 0
    # 모든 가능한 3장 카드 조합을 탐색
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                current_sum = cards[i] + cards[j] + cards[k]
                # 현재 조합의 합이 M을 넘지 않으면서 최대 합을 갱신
                if current_sum <= M:
                    max_sum = max(max_sum, current_sum)
    return max_sum

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

# 결과 출력
print(blackjack(N, M, cards))