백준 2798번 블랙잭 파이썬 풀이

[Python] 백준 알고리즘 온라인 저지 2798번 블랙잭

백준 2798번 문제

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

2798번: 블랙잭

브루트 포스 단계의 문제로 3장의 카드 조합을 모두 더하고 그 값이 m에 가장 근사한 값을 출력하는 문제이다. 문제의 난이도는 쉬운 편이었다. 이 문제 같은 경우는 블랙잭 게임을 구현하는 문제와도 같아서 의사 코드를 작성 후 코드를 작성했다.

---

코드

n, m = map(int, input().split())
cards = list(map(int, input().split()))
result = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if cards[i] + cards[j] + cards[k] > m:
                continue
            else:
                result = max(result, cards[i]+ cards[j] + cards[k])
print(result)

 

의사코드(pseudocode)

1. n과 m값 받기
2. 리스트에 카트 넣기
3. 모든 조합 더하기
4. if문을 활용해 m보다 작거나 같은 값은 값 변수로 저장
5. 모든 계산이 끝났을때 변수 출력

---

브루트 포스

• 조합 가능한 모든 경우를 하나씩 대입하는 방법으로 완전 탐색으로도 불린다.
• 이 방법으로 암호를 해독하기도 한다. (해킹)
• 시간 복잡도는 길이(n)와 조합(m)에 의해 결정되고 O(m^n)이다.
• 시간이 많이 걸리지만 찾을 확률은 100%에 가까운 방법이다.

---

풀이

의사 코드와 같이 입력 값을 각 n과 m에 지정해주고 n만큼의 길이의 카드를 cards로 지정했다. 그리고 result라는 변수를 지정해 나중에 계산이 끝나고 출력할 수 있도록 했다.

3장의 카드의 합을 모든 조합으로 구하기 위해서 for문을 3번 사용하였다. 즉 cards = [5, 6, 7, 8, 9] 일 때

 

• 첫 번째 for문 i = 5로 시작해 하나씩 뒤부터 시작하는 for문 두 개를 더 작성한다.
• 3번째의 for문까지 바로 내려가 (5, 6, 7), (5, 6, 8), (5, 6, 9)... 의 조합을 계산하게 된다.
• 그 후 j = 7이 되고 이러한 방식으로 진행된다. (혹시 궁금해하시는 분들이 있다면 디버그를 활용해보세요.)
• 즉 상위의 for문의 변수가 하나씩 상승하며 모든 조합을 구할 수 있다.

그 후 if문을 활용하여 더한 값이 m보다 크다면 변수에 저장하지 않고 작거나 같다면 result에 저장하여 새로운 값과 비교하여 더 큰 값을 구하는 Max함수를 이용하여 result의 값을 새롭게 저장한다. 모든 계산이 끝나면 result를 출력한다.

---

풀이 결과