백준 2798 - 블랙잭 (Python)

문제

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

 

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

 

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

 

첫번째 풀이 (조합 라이브러리 사용)

from itertools import combinations

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

combs = list(combinations(cards, 3))

max_sum = 0
for comb in combs:
    if sum(comb) > max_sum and sum(comb) <= m:
        max_sum = sum(comb)

print(max_sum)

브루트포스를 사용하여, 모든 경우의 수를 고려해본다.

구해야 할 것은 n장의 카드 중 3장의 합이 나오는 모든 경우의 수 인데, 이번 풀이에서는 combinations 라이브러리를 이용하여 풀이했다.

3장을 고르는 cards 리스트를 만들고, 각 원소의 합 (3장의 합) 중 M을 넘지 않는 max 값을 구한다.

 

두번째 풀이

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

result = 0

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if cards[i]+cards[j]+cards[k] > m:
                continue
            else:
                result = max(result, cards[i]+cards[j]+cards[k])
print(result)

조합 라이브러리를 사용하지 않는 풀이다.

간단히 1,2,3,4,5 카드가 있으면

1+2+3, 1+2+4, 1+2+5, 1+3+4, 1+3+5,,, 이런식으로 1<=i<j<k<=n 의 합을 구해주면 되기 때문에

3중 for문을 이용하였다.