8. 백준 코딩테스트 2798번 문제 python

이번에는 브루트포스(Brute force)의 문제 블랙잭을 풀어보았다. 정답률은 45.6%정도로 다소 높은편이다.

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

2798번: 블랙잭

 

들어가기 전.

 

 

브루트포스(Brute Force)는 조합 가능한 모든 경우를 대입하는 해결법을 말한다. 간단하게 4자리 비밀번호를 맞추기 위해서 0000~9999까지 모든조합을 대입하는 방법을 브루트포스라고 한다.

 

블랙잭이란 카드게임은 숫자카드에 쓰여있는 숫자와 10, J, Q, K 를 10 그리고 A를 1 또는 11로 계산하여 21에 최대한 가까운 수를 만드는 게임이다. 단 두장으로만 21을 만드는 경우(A를 포함하여 10, J, Q, K인 경우)가 블랙잭이다. 21을 넘게되는 경우는 무조건 패배이다.

 

 

해결방법.

 

여기서는 카드 3장으로 주어진 카드의 숫자와 주어진 숫자에 최대한 가깝게 만드는 문제이다. 

 

만약 한장의 카드를 선택한다면 어떻게 할까? 주어진 카드를 한장한장 비교하며 선택을 할 것이다. 

그렇다면 두장의 카드를 선택한다면 어떻게 할까? 한장의 카드를 맨 처음카드에 고정시키고 다른 카드 한장한장 비교하며 선택을 할 것이다.

버블정렬을 생각하면 아주 좋을 것 같다.

세장의 카드를 선택한다면? 두장의 카드를 고정하고 한장한장 비교하다 모두 비교하면 두번째 카드를 한칸 옮기고 다시 하나하나 비교할 것이다.

 

코딩을 해보자.

card_count, limit = map(int, input().split())
card_list = list(input().split())
maxi = 0

#a는 첫번째 카드, b는 두번째 카드, c는 세번째 카드이다.
#첫번째 카드는 가장 우측에 도달했을 때에는 두 카드도 우측에 도착한 상태이므로 -2를 해준다.
for a in range(0, len(card_list)-2):
    # 두번째 카드가 시작할 때에는 첫번째 카드가 좌측에 있으므로 +1를 해준다.
    # 두번째 카드는 가장 우측에 도달했을 때에는 한장의 카드만 우측에 도착한 상태이므로 -1를 해준다.
    for b in range(a+1, len(card_list)-1):
        # 세번째 카드가 시작할 때에는 첫번째,두번째 카드가 좌측에 있으므로 +2를 해준다.
        # 세번째 카드는 가장 우측에 도달했을 때에는 가장 우측에있으므로 그대로 둔다.
        for c in range(b+1, len(card_list)):
            total = int(card_list[a]) + int(card_list[b]) + int(card_list[c])
            if total <= limit:
                if total > maxi:
                    maxi = total
                    
print(maxi)