[백준][python] 2798 블랙잭

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

2798번: 블랙잭

풀이 과정 1

1. N장의 카드 중에서 3장의 카드를 고르는데 3장의 카드의 합이 M을 넘지 않으면서 최대한 가까워야 한다

2. 두 번째로 입력받은 cards의 리스트를 처음부터 끝까지 다 돌아야 하는 완전탐색 문제

cards = ['5', '6', '7', '8', '9']
          0    1    2    3    4 
ijk
012
013
014
023
024
034
123
124
134

3. cards의 인덱스로 모든 경우의 수를 따졌을 때 위처럼 나오는데 i = 0 ~ 2 / j = 1 ~ 3/ k = 2 ~ 4 이기 때문에

아래와 같이 range범위를 만들 수 있다 

4. 삼중 for문으로 돌면서 만약에 i, j, k의 값이 모두 다르다면 new_cards에 각 위치를 append

===== 여기까지가 위의 경우의 수를 찾아서 더한 후 new_cards 리스트에 새로 만든 경우=====

5. new_cards 리스트를 for문 돌려서 21보다 작거나 같은 경우에만 card변수 리스트에 append

6. card 리스트의 요소 중 가장 큰 값(=M과 가장 가까운 카드)을 출력하면 끝

n, m = map(int, input().split())
cards = list(map(int, input().split()))
new_cards = []
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            if i != j != k:
                new_cards.append(cards[i] + cards[j] + cards[k])
# print(new_cards)
card = []
for i in new_cards:
    if i <= m:  # 21보다 작거나 같을 경우
        card.append(i)  # card리스트에 append
print(max(card))

🌱 삼중 for문에서 모든 range범위를 5로 설정해도 같은 결과 값을 가질 수 있고

시간 복잡도 측면에서도 같은 효율을 낸다

➡️ 왜? 어차피 삼중 for문이라는 사실은 변함이 없으니까!

풀이 과정 2

1. [풀이 과정1]보다 간단함

2. 시간복잡도를 따져도 효율은 같다 

n, m = map(int, input().split())
num = list(map(int, input().split()))
new = []
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if (num[i] + num[j] + num[k]) <= m:
                new.append(num[i] + num[j] + num[k])

print(max(new))

 

---

리뷰

완전탐색을 배우고 적용해 본 문제인데 '처음부터 끝까지 다 살펴본다'라는 의미여서

이차원 리스트에 비하면 어렵지는 않은 문제?!