[백준 2798] 블랙잭 (Python)

👩🏻‍💻문제링크

[백준 2798] 블랙잭 (Python)

 

✍️Idea Sketch

플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

 

처음에 삼중 for문을 쓰면 구현은 되겠군 했다가, 성능이 별로일 것 같은데.. 설마 삼중 for문을 쓸까? 하는 생각에 백트래킹(dfs)을 써서 풀었다.
다른 분들의 코드를 확인한 결과, 삼중 for문으로 구현한 코드가 매우 많았다. (채점 시간도 내 것보다 짧았다..)

 

백트래킹 연습문제인 N과 M (2) 문제를 응용하면 쉽다.

전체적인 흐름은 다음과 같다.

dfs()에서 플레이어는 모든 카드를 순차적으로 확인하며 고를지 말지 결정한다.
플레이어가 3장을 고르면,
isMax()에서 문제의 조건을 만족하는지 확인하여 maX를 업데이트한다.

 

✍️소스코드

import sys


def isMax(num):
  global maX
  if num <= m and num > maX:
    maX = num


def dfs(v, cnt):
  if cnt >= 3:  # 플레이어가 3장을 고른 경우
    isMax(sum(lst))
    return
  if v >= len(cards):  # 모든 카드를 확인한 경우
    return

  lst.append(cards[v])
  dfs(v+1, cnt+1)  # v번째 카드를 고른 경우
  lst.pop()
  dfs(v+1, cnt)  # v번째 카드를 고르지 않은 경우


if __name__ == "__main__":
  n, m = map(int, sys.stdin.readline().rstrip().split())
  cards = list(map(int, sys.stdin.readline().rstrip().split()))

  lst = []  # 플레이어가 고른 카드
  maX = 0  # M을 넘지 않으면서 M과 최대한 가까운 카드의 합

  dfs(0, 0)
  print(maX)