백준 #2798: 블랙잭 [Python]

 

접근법

---

브루트 포스의 문제는 조금은 무식하게 보일지 모르지만 모든 경우의 수를 보는 것이 맞다.

 

물론 지금 이 문제는 python의 itertools를 이용해서 조합을 통해 쉽게 풀 수도 있지만 알고리즘의 측면에서 풀어보자.

 

우선 필자는 아래 코드로 문제를 풀었다. 

 

 

N, M = map(int,input().split(' '))
card = list(map(int,input().split(' ')))
res = set()
for i in range(N-1):
    
    pick = card[i:i+2]                         # 카드 두 장을 먼저 뽑습니다
    other = [x for x in card if x not in pick] # 뽑은 두 장의 카드를 제외한 카드를 리스트에 담습니다.
    
    for j in other:
        
        if M >= sum(pick,j) :                  # 규칙 상 먼저 뽑은 두 장의 카드와 나머지 한장의 카드를
                                               # 더해줄 때, 지정한 값보다 작은 값만 중복을 방지하기
            res.add(sum(pick,j))               # 위해서 set형의 변수에 값을 추가합니다.

print(max(res))                                # 가장 큰 값을 출력합니다.

 

필자의 로직은 옆에 주석 처리한 것처럼 두 장의 카드를 먼저 뽑은 뒤에 뽑힌 카드를 제외한 나머지 카드를 다른 list에

 

담아 놓는다. 그리고 모든 경우에 대해서 set형의 변수에 sum값을 추가하도록 했는데 결과는 오답이다.

 

내가 놓친 부분은 그냥 pick을 연속된 두장을 뽑고 나머지 카드를 모두 더하면 된다고 생각했는데, 이 생각이 잘못이다...

 

연속된 카드가 아닌 것들도 뽑아주었어야 했다. 

 

틀린 코드를 먼저 공개한 이유는 바로 모든 경우의 수를 봐야한다는 것을 강조하기 위함이다.

 

따라서, 연속되도록 뽑는 것이 아니라 하나의 카드를 고르고, 또 나머지 카드를 고르고 마지막으로 남은 카드를 

 

골라가면서 ... 그러니까 3중 for문을 이용해야한다. 바로 아래와 같이 😂

풀이

---

N, M = map(int, input().split())
card = list(map(int, input().split()))
card.sort()
res = 0

for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            s = card[i] + card[j] + card[k]
            if s > M:
                break
            else:
                res = max(res, s)
print(res)

 

Bonus : itertools를 이용한 조합을 이용한 방법

 

import itertools
N, M = map(int, input().split())
card = list(map(int, input().split()))
pick = itertools.combinations(card, 3)

res = 0
for i in pick:
    if sum(i) <= M:
        if res < sum(i):
            res = sum(i)
print(res)

 

조합만세

 

@문제 출처 : 백준