[백준] 블랙잭 (Python)

✏️ 문제

2798번: 블랙잭

✏️ 풀이

주어진 카드 중 3개를 고른 합이 M을 넘지 않으며 최대한 M과 가까워야 한다.

중복해서 고를 수 없고 순서 관계없이 선택하므로 조합을 사용한다.

✏️ 코드

import itertools

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

min = m
min_sum = 0

for i in itertools.combinations(nums, 3):
    diff = m - sum(i)
    if diff == 0:
        min = 0
        min_sum = sum(i)
        break
    elif diff > 0:
        if min > diff:
            min = diff
            min_sum = sum(i)

print(min_sum)

시간복잡도를 줄이기 위해 diff가 0이면 차이가 최소이므로 바로 출력하고 break하였다.