백준 알고리즘 2798 (블랙잭) - python

[문제] 백준 알고리즘 2798 (블랙잭)

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

2798번: 블랙잭

 

N개의 수가 주어진 배열에서 3개를 선택해 M에 가까운 수를 만드는 문제이다.

주의할 점은 그 수의 합이 M을 넘어가면 안된다. 

 

접근 방식은 2가지로 해봤다.

1. 배열적인 접근으로 3중 for문으로 접근한 방식이고,

2. DFS로도 가능해보였다.

 

1. 배열의 한 칸 오른쪽을 접근하면서 효율적으로 for문을 작성했다.

배열의 i, i+1, i+2 번째 값을 더해보면서 M을 넘어가지 않는 최대값을 구헀다.

 

[Code]

N, M = map(int, input().split())
L = list(map(int, input().split()))
max_val = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            _sum = L[i] + L[j] + L[k]
            if _sum > M:
                continue
            if abs(M - max_val) > abs(M - _sum):
                max_val = _sum
print(max_val)

 

2. DFS로 가능한 순열 조합을 구한 뒤에, 더한 값 중에 M을 넘어가지 않는 최대값을 구했다.

 

[Code]

N, M = map(int, input().split())
L = list(map(int, input().split()))
visited = [False] * N
out = []
all_case = []

def solve(depth, idx, N, M):
    if depth == 3:
        sum_out = sum(out)
        if sum_out <= M:
            all_case.append(sum_out)
        return
    for i in range(idx, N):
        out.append(L[i])
        solve(depth+1, i+1, N, M)
        out.pop()

def print_val():
    max_val = 0
    for i in all_case:
        if abs(M - max_val) >= abs(M - i):
            max_val = i
    print(max_val)

solve(0, 0, N, M)
print_val()