문제

링크

풀이

굉장히 쉽게 푼 문제이다. 조합을 생각하여 문제를 푼다면 쉽게 풀 수 있다.

1. N장의 카드에서 3개를 뽑는 모든 조합의 경우를 만든다.

2. 각 경우의 합을 계산한 후 M을 넘지 않으면서 가장 최댓값을 구한다.

백트래킹 방법으로도 코드를 구현해봤으나 시간초과가 났다... 조합으로 푸는 것과 시간복잡도가 비슷할 것 같은데, 왜그런지 코드를 다시 수정해야할 것 같다.

코드

import sys
from itertools import combinations

input = sys.stdin.readline
N, M = map(int, input().split())
cards = list(map(int, input().split()))

result = 0
for case in combinations(cards, 3):
    mid_sum = sum(case)
    if mid_sum <= M and mid_sum > result:
        result = mid_sum

print(result)