[백준] 블랙잭 (2798번 파이썬)

winner winner chicken dinner!

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

2798번: 블랙잭

 

이번 문제는 재미있는 카드게임인 블랙잭이다!

 

처음 문제를 보고 나는 겁을 먹었다.

요즘 내 수준보다 높은 문제들을 많이 도전하다보니 문제를 읽고 적용해야할 알고리즘 기법이 떠오르지 않는다면 겁부터 먹게되는 것 같다.

하지만 이 문제는 사실 쉬운 문제로 시간 복잡도를 크게 신경 쓸 필요가 없었다.

그래서 알고리즘 분류도 브루트포스로 되어있다.

3개의 카드를 어떤식으로 뽑아올지 생각하다가 문득 여러개의 버튼으로 구성된 자물쇠를 따는 과정이 생각났다.

앞의 버튼 3개를 누른 뒤 마지막 버튼만 바꿔가며 누르고 한바퀴 돌면 3번째 자리를 한 칸 옮긴 후 마지막 버튼을 다시 움직여보는..

마치 4자리 비밀번호가 있을 때 0000~9999를 다 눌러서 푸는.. 뭐.. 그런 문제이다.

당연히 진행되는 과정은 0000, 0001, 0002, ..., 0009, 0010, 0011 이런식으로 숫자를 하나씩 올리면서 맞추는 것이고 이것을 숫자가 아닌 카드 개수로 보고 뽑아야하는 카드가 3개니까 3개의 정답 자리를 여러개의 카드로 대입해보는 방식으로 풀어야 겠다고 생각했다.

(글로 설명하려니까 매우 복잡해지고 난해해졌다.)

 

각설하고 결론만 미리 말하면 3중 for문을 사용하면 풀 수 있다는 것이다.

(숏코딩을 보면 한줄컷하던데 우리는 그런 사람이 아니니까 pass 하자..)

 

 

 

생각해야 할 점은 2가지 정도 된다.

 

1. 어떤식으로 카드를 선택할지

이 부분은 앞에서 언급한 것과 같이 나는 3중 for문을 통해 모든 경우의 수를 확인하는 알고리즘을 구현했다.

다만 고려할 부분은 3개의 for문에서 중복으로 카드를 뽑지 않도록 처리해줘야한다는 것이다.

이 점은 모든 for문에서 중복을 검증할 필요 없이 2번째 for문에서는 첫번째 카드와 중복되지 않게하고 3번째 for문에서는 첫번째, 두번째 카드와 중복되지 않게 해주면 된다.

 

2. 최선의 M과 근접한 값 찾기

이 부분도 매우 중요하다.

어떤식으로 특정 3개의 카드를 더한 값이 m과 근접한지 비교하기 위한 방식을 생각해내야한다.

그래서 나는 "M과 3개의 카드 합 간의 차이가 적을 수록 M의 근사한 값을 가진다." 라는 점을 이용했다.

 

 

import sys
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
best_gap = 300001
for a in range(n): # 첫번째 카드
    for b in range(n): # 두번째 카드
        if b == a:
            continue

        for c in range(n): # 세번째 카드
            if c == b or c == a:
                continue
            result = arr[a] + arr[b] + arr[c]
            if result <= m:
                gap = m - result
                if gap < best_gap:
                    best_gap = gap
                    blackjack = result
print(blackjack)