2798번: 블랙잭
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장
www.acmicpc.net
n, m = map(int,input().split())
card_list = list(map(int,input().split()))
visited = [False]*n
min_diff = float("inf")
def dfs(total,count):
global min_diff
global answer
diff = m - total
if count == 3:
if diff >= 0 and diff < min_diff:
min_diff = diff
answer = total
return
for i,value in enumerate(card_list):
if not visited[i]:
visited[i] = True
dfs(total+value,count+1)
visited[i] = False
dfs(0,0)
print(answer)
이번 문제는 N장의 카드 중에서 카드 3장을 골라 그 합이 M과 가장 가까운 수를 구하는 문제이다. (단, M을 넘어서는 안된다.)
여러 풀이에서는 3중 for문으로 풀이했는데, 나는 dfs 방식으로 풀이하는게 편해서 dfs 방식으로 풀이하였다 :)
'Algorithm > BruteForce' 카테고리의 다른 글
[백준 20164번] 홀수 홀릭 호석 (0) | 2023.12.28 |
---|---|
[백준 1018번] 체스판 다시 칠하기 (0) | 2023.10.18 |
[프로그래머스 Lv.1] 모의고사 (0) | 2023.09.29 |
[프로그래머스 Lv.1] 최소직사각형 (0) | 2023.09.28 |
[백준 1476번] 날짜 계산 (0) | 2023.05.04 |