[Algorithm] 백준 2798 - 블랙잭

문제

예제 입/출력

풀이

N장의 카드 중에서 3장을 골라야 한다. M을 넘지 않으면서 M에 최대한 가까운 3장의 합을 구해서 출력하는 문제이다.

3장을 골라 M과 최대한 가까워야하니 입력된 카드를 sort(reverse=True)를 이용하여 내림차순 정렬을 하고 문제를 푼다.

코드

N, M = map(int, input().split())
arr = list(map(int, input().split()))
answer = 0



arr.sort(reverse=True)

for i in range(N):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            if arr[i] + arr[j] + arr[k] == M:
                answer = arr[i] + arr[j] + arr[k]
                break
            elif arr[i] + arr[j] + arr[k] < M and arr[i] + arr[j] + arr[k] > answer :
                answer = arr[i] + arr[j] + arr[k]

            elif arr[i] + arr[j] + arr[k] > M:
                continue

print(answer)

N, M을 입력받고 카드를 입력받아 리스트화 하여 arr에 저장한다.
arr.sort(reverse=True)로 내림차순 정렬한다.

완전 탐색을 이용할 것이므로 3중 반복문을 사용한다.
최대한 가까운 합을 구해야 하므로 카드 3장을 더했을 때, 같으면 더 이상 볼 필요가 없기 때문에 answer에 값을 저장하고 break문으로 반복문을 빠져나온다.

최대한 가까운 합을 구해야 하므로 M과 같지 않아도 answer에 값을 저장하고 arr[i] + arr[j] + arr[k] > answer의 조건을 통해 최대의 answer로 갱신할 수 있도록 한다.