백준_2798_블랙잭/Using_python_파이썬

Problem

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

2798번: 블랙잭

About Problem

가장 중요한 부분이 N장의 카드에서 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력을 해야한다.

세장의 카드 밖에 없으므로 input에 범위에 따라서 어떤 알고리즘을 쓸지 결정한다

Input

N이 100이므로 최대로 했을 때 100 * 99 * 98 이므로 10만정도 된다. 그러므로 dfs, 브루투포스 알고르짐을 쓰기에 적합하다.

Output

결국 M에 최대한 가까운 카드 3장의 합만 출력을 하면된다

Code

from sys import stdin

# 부분순열을 구하기 위해서 브루투포스를 이용해서 전체 탐색을 한다.
def dfs(n, i, total): # n은 카드선택 횟수, 고른 카드 다음 idx, total은 이때 동안 총합
    global max_num
    # 가지치기(total이 M을 넘으면 return)
    if total > M:
        return
    
    # 종료조건
    if n == 3:
        # total값을 비교해서 maximun 갱신
        if total > max_num:
            max_num = total
    
    # 부분수열을 구하기 위해서 반복 재귀
    else:
        for j in range(i, N):
            dfs(n+1, j+1, total + lst[j])


# 입력값 받기
N, M = map(int, stdin.readline().split())
lst = list(map(int, stdin.readline().split()))
max_num = 0

# 부분순열 탐색 시작
for i in range(N-2):
    dfs(1, i+1, lst[i])

print(max_num)