[백준] 2798 파이썬(python) : 블랙잭

2790번 : 파이썬

 

 

 

입력값 m에 가장 가까우면서도 넘지 않는값을 구하는 문제다. 브루트포스로 풀어야 한다는 생각이 들었다. 3중 for문으로 O(n³)으로 해결하는데 입력값 n이 100을 넘지 않기 때문에 1,000,000 최대값이 백만이어서 1초안에 시간을 넘길 수 있다.

 

 

n, m = map(int, input().split())
array = list(map(int, input().split()))
result = 0
sum = 0
for i in range(len(array)): #1
    for j in range(i+1, len(array)): #2
        for k in range(j+1, len(array)): #3
            sum = array[i] + array[j] + array[k]
            if sum > result and m >= sum: #4
                result = sum
print(result)

 

 

#1, 2, 3 : 처음 지정해줬던 수를 또 지정해서 더 할 수는 없기 때문에 j는 i+1로 k는 j+1로 지정해준다.

#4 : 입력값 m을 넘지않고 가장 큰수를 찾는다.

 

 

다른 풀이)

import sys
from itertools import combinations
n, m = map(int, sys.stdin.readline().split())
cards = list(map(int, sys.stdin.readline().split()))
res = 0
for card in combinations(cards, 3): #1
    if sum(card) <= m: #2
        res = max(res, sum(card)) #3
print(res)

 

 

itertools의 combinations를 이용했다.

#1 : 입력받은 리스트 cards에서 3개의 카드를 뽑는다. 이때 순서는 상관없으므로 조합을 이용한다.

#2 : 3개의 카드의 합이 m보다 작거나 같을때

#3 : 가장 큰 카드의 합을 res에 저장 후 출력