[Python/백준] 2798. 블랙잭

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

리스트

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

 

입력 : 카드의 개수 N과 최대 합 M, 그리고 카드들 목록

출력 : M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합

예제 입력 1 
5 21
5 6 7 8 9
예제 출력 1 
21

각 카드는 양의 정수.

딜러는 N장 뽑아서 숫자 M 크게 외침.

플레이어는 N장 중 3장을 골라 합이 M을 넘지 않으며 최대한 크게 만들어야 함.

입력 : N(카드 개수), M과 카드 목록

출력 : 내가 뽑은 카드 3장의 합

---

1차 풀이

# 1차 풀이
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
cards = list(map(int, input().split()))

sum = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            temp = cards[i] + cards[j] + cards[k]
            if temp <= m and temp > sum:
                sum = temp
        
print(sum)

- 브루트 포스로 O(n^3)으로, C스럽게 풀어서 아쉽다.

- 다른 문제들 풀고 다시 와서 개선하자.

2차 풀이

# 2차 풀이
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
cards = list(map(int, input().split()))

sum = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            temp = cards[i] + cards[j] + cards[k]
            if sum < temp <= m:
                sum = temp
        
print(sum)

- 정답을 보고, range() 인덱스를 좀 더 효율적으로(덜 조회하게끔) 수정했다.

- 추가로, C와 달리 파이썬은 부등호를 한 번에 사용 가능하단거 기억하자!

---

250217 재풀이

import sys
input = sys.stdin.readline

# n장 카드 중에 3장 고를 건데, m을 넘지 않으면서 m에 최대한 가깝게 만들고 싶음.
# n이 별로 안 커서 반복문 돌려도 될듯.

n, m = map(int, input().split())
cards = list(map(int, input().split()))

# 밖에서부터 안으로 1 2 3 느낌으로
total = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            temp = cards[i] + cards[j] + cards[k]
            if total < temp <= m:
                total = temp

print(total)