[Python] 백준 2798 블랙잭

 

문제 분석

• 카드 합이 21이 넘지 않는 한도 내에서 카드의 합을 최대한 크게 만드는 게임
• 각 카드에는 양의 정수가 쓰여 있음
• 그 다음 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓고
• 그 후 딜러는 숫자 M을 외침
• 플레이어는 제한 시간 안에 N장의 카드 중 3장의 카드를 고르는데
• 플레이어가 고른 3장의 카드가 M을 넘지 않으면서 M과 최대한 가까워야 함
• N장의 카드에 숫자가 써 있을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합 출력

 

코드 설계

• 어떻게 M을 넘지 않으면서 M과 최대한 가까운 수들의 합을 구할것인가?
• 완전 탐색 : 3개를 뽑아서(순서x,  중복x) 합을 구하는데 그 중 M을 넘지 않으면서 M과 가장 차이가 적은 수 print
• 조합

 

정답 코드

import sys
from itertools import combinations
input = sys.stdin.readline

n, m = map(int, input().split())
cards = list(map(int, input().split()))

ans = []

for r in combinations(cards, 3) :
    if sum(r) <= m :
        ans.append(sum(r))

print(max(ans))

 

다른 사람 코드 1

import sys
from itertools import combinations

input = sys.stdin.readline

# N, M 입력
N, M = map(int, input().split())

# N장의 카드 입력
cards = list(map(int,input().split()))

# 정답 저장 변수 선언
ans = 0

# N개 중 3개 고르는 조합 계산
for com in combinations(cards, 3):
    card_sum = sum(com)
    # M을 넘지 않으면서 M에 가장 가까운 카드의 합 구하기
    if card_sum <= M:
        ans = max(card_sum, ans)

# 원하는 형태로 출력
print(ans)

 

다른 사람 코드 2 - 모든 경우를 다 따지는 경우

N, M = map(int,input().split())
nums = list(map(int,input().split()))
max=0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            sum = nums[i]+nums[j]+nums[k]
            if(sum<=M and sum>max):
                max=sum
print(max)