[DFS/BFS/완전탐색] 2798번 - 블랙잭(완전탐색)

[백준] 2798번 - 블랙잭

풀이 시간: 15분 이내

아주 쉽게 풀 수 있었고 완전탐색으로 풀어야하는 문제다.

(풀이1) combinations 이용

1) 문제 해결 아이디어

itertools 모듈의 combinations 라이브러리를 이용하여 풀 수 있다.

 

2) 소스코드

from itertools import combinations

# n: 카드 개수,m: 기준 숫자
n, m = map(int, input().split())
card = list(map(int, input().split()))
max_res = 0  # M에 최대한 가까운 카드 3장의 합

# n개에서 3장 뽑아 m에 가장 가까운 3장의 합 찾기
for c in list(combinations(card, 3)):
  res = sum(c)
  if(res <= m and max_res < res):
    max_res = res
print(max_res)

 

(풀이2) 3중 for문 이용

1) 문제 해결 아이디어

3중 for문을 이용하여 모든 경우의 수를 구하여 푸는 BruteForce 문제다.

첫번째 선택값(i)의 범위: 0 ~ (n -2)

두번째 선택값(j)의 범위: (i + 1) ~ (n - 1)

세번째 선택값(k)의 범위: (j + 1) ~ n

 

2) 소스코드

from itertools import combinations

# n: 카드 개수,m: 기준 숫자
n, m = map(int, input().split())
card = list(map(int, input().split()))  # n장의 카드
max_res = 0  # M에 최대한 가까운 카드 3장의 합
res = 0

# n개에서 3장 뽑아 m에 가장 가까운 3장의 합 찾기
for i in range(0, n - 2):
  for j in range(i + 1, n - 1):
    for k in range(j + 1, n):
      res = card[i] + card[j] + card[k]
      if(res <= m and max_res < res):
        max_res = res
print(max_res)