[백준] 2798번: 블랙잭

블랙잭

문제

변형된 블랙잭이다. 딜러가 N장의 카드를 숫자가 보이게 바닥에 놓는다.
딜러는 숫자 M을 말한다.
플레이어는 N장의 카드 중에서 3장의 카드를 골라서 합이 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
딜러가 5장(N장)의 카드를 놨다고 하자.

💡 5 6 7 8 9

딜러가 21(M) 을 외쳤다.

플레이어는 5장(N장) 중에서 3장을 뽑아야 한다. 21을 넘지 않으면서도 최대한 가깝게 해야한다.
답은 딱 21을 맞추는 6, 7, 8 을 뽑는 것이다. 따라서 3장의 합 21을 출력해주면 답이다.

어떻게 풀면 좋을까?

1. 단순하게 for문 돌려서 567, 568, 569, 678 .... 그리고 M을 넘지 않으면서 최대값을 저장해가면서 하면 될까?
   • 딜러가 보여줄 카드의 개수 N이 최대 100장까지 간다. 시간 초과가 예상된다...
2. 솔직히 위의 방법 말고 모르겠다. 파이썬에 수를 조합해주는 라이브러리가 있던걸로 기억하는데 그걸 사용하면 좀 좋을까?

풀이

💡 조합 - combinations 활용

💡 부르트포스 알고리즘

combinations는 순서를 고려하지 않고 뽑는다. [A,B] 를 뽑았다면 [B,A]는 고려하지 않는다.

from itertools import combinations

def main():
    test = ['A', 'B', 'C']
    print(list(map(''.join, combinations(test, 2))))
		# ['AB', 'AC', 'BC']

if __name__ == '__main__':
    main()

실제로 문제에서 어차피 6, 7, 8 을 더하나, 7, 6, 8 을 더하나 똑같기 때문이다.

한줄씩 풀이! 풀이는 예제 입력을 토대로 작성되었습니다.

def main():
    from itertools import combinations
		
		# map의 결과물을 N,M 과 같이 언패킹 할 수 있다.
    N, M = map(int, input().split())
		
		# 5, 6, 7, 8, 9 와 같은 입력을 list에 받아오기
    card_list = list(map(int, input().split()))

		# 결과물이 될 최대 수
    biggest_num = 0
		
		# combinations의 결과물들을 하나씩 for문으로 접근한다.
    for cards in combinations(card_list, 3):
				# cards는 (5, 6, 7), (5, 6, 8), (5, 6, 9) ... 와 같은 결과를 가진다.
        cards_sum = sum(cards)
				# 만약 나의 현재 최대 값(biggest_num)이 pick_sum 보다 작으면서
				# pick_sum이 딜러가 말한 M 보다 작거나 같다면 biggest_num을 갱신시킨다.
        if biggest_num < cards_sum <= M:
            biggest_num = cards_sum 
    print(biggest_num)

• 문제의 예제 입력을 입력 시 card_list의 결과물
  

    # 예제 입력은 아래와 같다.
    # 5 21
    # 5 6 7 8 9
    
    (5, 6, 7)
    (5, 6, 8)
    (5, 6, 9)
    (5, 7, 8)
    (5, 7, 9)
    (5, 8, 9)
    (6, 7, 8)
    (6, 7, 9)
    (6, 8, 9)
    (7, 8, 9)
    
    # 이 결과물들을 for문에서 하나씩 접근하는 것이다.

• 다른 순열, 조합
  

    def main():
        from itertools import combinations, permutations, product, combinations_with_replacement

        arr = [10, 20, 30]

    		# **순열** : arr 에서 **순서가 다르면 다른거다**. 인자 2는 2개를 뽑으라는 뜻.
    		# [(10, 20), (10, 30), (20, 10), (20, 30), (30, 10), (30, 20)]
        print(list(permutations(arr, 2)))

    		# **중복 순열** : arr 에서 **순서가 다르면 다른거**고, **중복도 허용**한다.
    		# [(10, 10), (10, 20), (10, 30), (20, 10), (20, 20), (20, 30), (30, 10), (30, 20), (30, 30)]
        print(list(product(arr, repeat=2)))

    # =============================================================================================

    		# **조합** : **순서가 달라도 같은거**다.
    		# [(10, 20), (10, 30), (20, 30)]
        print(list(combinations(arr, 2)))

    		# **중복 조합** : **순서가 달라도 같은**건데, **중복은 허용**한다.
    		# [(10, 10), (10, 20), (10, 30), (20, 20), (20, 30), (30, 30)]
        print(list(combinations_with_replacement(arr, 2)))