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))
'Algorithm > Mastered' 카테고리의 다른 글
[프로그래머스]타겟 넘버 (0) | 2023.11.15 |
---|---|
[LeetCode] 1491. Average Salary Excluding the Minimum and Maximum Salary (0) | 2022.09.18 |
[LeetCode]1523. Count Odd Numbers in an Interval Range (0) | 2022.09.17 |
for 문을 사용하지 않고 홀수의 개수 구하기 (0) | 2022.09.15 |
댓글