[브론즈2]백준 2798번(블랙잭) - 코테공부 28일차(2025.02.19)

문제유형

조합 알고리즘

풀이 방법 도출 과정

1. 브루트 포스를 사용해서 푼다. 모든 3개의 조합을 만들고 그것의 값이 M의 값 이하인 것 중 가장 크기가 큰 것을 찾아 보여주는 방식으로 하도록 하겠다.

시간 복잡도

시간 복잡도는 모두 O(nC3)이다. 하지만 최악의 경우가 100이기 때문에 1억번이 넘지 않아 시간복잡도는 괜찮다. 

코드 및 간단설명

조합을 사용해서 문제를 풀었다.

from itertools import combinations

N, M = map(int, input().split())
lst = list(map(int, input().split()))
result = []

for num in combinations(lst, 3):
    if sum(num) <= M:
        result.append(sum(num))
        
print(max(result))

다른 풀이

1) 투 포인터(two pointer) 기법 사용

투 포인터(two pointer) 기법을 사용하여 문제를 풀수도 있다. 

N, M = map(int, input().split())
cards = list(map(int, input().split()))
cards.sort()
best = 0

for i in range(N - 2):
    left, right = i + 1, N - 1
    while left < right:
        total = cards[i] + cards[left] + cards[right]
        if total > M:
            right -= 1
        else:
            best = max(best, total)
            # M과 정확히 일치하면 더 이상 개선할 수 없으므로 바로 종료
            if best == M:
                print(best)
                exit(0)
            left += 1

print(best)