[python] 백준 2789 - 블랙잭

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

2798번: 블랙잭

 

 

핵심 개념

Binary Search

Combination

 

부가 개념

파이썬 삼항 연산자

list를 key값으로 배열 시 key에 함수를 사용하기

 

풀이

from itertools import combinations

def binary_search(array, start, end, target):
  if(start >= end):# 종료조건
    return sum(array[start])

  mid = (start + end) // 2 + 1 if (start + end) % 2 == 1 else (start + end) //2

  # if sum(array[mid]) == target:
  #   return sum(array[mid])

  if sum(array[mid]) > target:
    end = mid - 1
  
  if sum(array[mid]) <= target:
    start = mid

  return binary_search(array, start, end, target)

[card_num, target] = list(map(int, input().split()))
card_list = list(map(int, input().split()))

card_combi = list(combinations(card_list, 3))

card_combi.sort(key=sum)

print(binary_search(card_combi, 0, len(card_combi) - 1, target))

 

1. input으로부터 카드 개수 car_num, 목표 숫자 target, 구성 카드 리스트 card_list를 불러온다.

2. combinations을 사용하여 전체 카드에서 3개의 카드를 뽑는 조합의 경우를 card_combi에 저장한다.

3. card_combi를 sum 함수의 값에 따라 정렬한다.

4. card_combi와 target을 이용하여 binary search를 수행한다.