[백준]2798번 블랙잭 - 완전 탐색

 

n, m = map(int, input().split())

num = list(map(int, input().split()))
length = len(num)
ans = 0
# 3중 포문을 통하여 차례로 탐색
for i in range(length - 2):
    for j in range(i + 1, length - 1):
        for x in range(j + 1, length):
            if num[i] + num[j] + num[x] > m:  # 3개를 더한 값이 크다면 넘어감
                continue
            else:  # m 보다 크지 않다면 저장된 값과 새로 더한 값중 큰것을 선택
                ans = max(ans, num[i] + num[j] + num[x])
print(ans)

 

코드 설명

모든 경우를 탐색하는 완전 탐색의 문제이므로 3중 반복문을 통해 문제를 해결할 수 있다.

첫번째 반복문은 길이의-2, 두번째는 길이-1, 세번째는 길이까지 반복을 수행한다.

만약 숫자 3개를 더한 값이 m 을 넘어갈 경우에는 반복문을 넘어가고 그렇지 않다면 원래 저장되어있는 값과 새로 구한 값을 비교해

큰 값으로 설정한다.

 

Point : 완전 탐색(브루트포스) 알고리즘은 모든 경우를 탐색해보아야 한다. 따라서 숫자 3개를 고르기 위한 3중 반복문을 사용하였으며 시작하는 위치를 i+1, j+1 처럼 해주어야 한다.