[백준][2798] 브루트포스, Combinations을 이용한 풀이

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

문제에 대한 이해:

다수의 카드에서 3개의 카드만 뽑아 카드에 적힌 수를 합한다.

세 개의 카드에 적힌 수의 합은 T, 이 합들만 보아놓은 집합을 S이라고 부르도록 한다.

S에 속한 T들은 M과 같거나 작아야 한다.

M과 같은 T가 있다면 M(=T)를 리턴하고, M보다 작은 T들 중에서 가장 M과 근소한 T를 리턴한다. 근소하다는 것은 M-T이 가장 작다는 것을 의미한다.

 

문제유형:

카드 세 개를 뽑을 경우의 수를 브루트포스로 추출한다. 이렇게 모든 조합을 찾아야할 경우 Python에서 지원하는 combinations를 쓰면 편리하다.

combinations는 주어진 자료형 안에 있는 원소로 만들 수 있는 모든 조합을 구해준다.

from itertools import combinations : 라이브러리 import

combinations(iterable 객체, 원하는 조합의 원소의 수 n) : iterable 객체에서 n개의 원소를 가진 모든 조합을 combinations 객체로 반환한다. 값을 보기 위해서는 list와 같은 다른 자료형태로 변환해주어야 한다.

 

2798에 활용 예시:

from itertools import combinations

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

def blackjack(ls):
    combis = [sum(x) for x in list(combinations(ls, 3))]
    if m in combis:
        return m
    else:
        sum_combis = [x for x in combis if x < m]
        return max(sum_combis)

print(blackjack(ls))