[BOJ] 2798. 블랙잭 / Brute Force / Python 풀이

얼마 전 PS 공부를 다시 시작했다.

참고할 풀이가 많은 백준으로 선택했고, 분류별, 단계별로 문제를 풀어보려고 한다.

시작으로 브루트포스 문제들을 먼저 풀어보고 있다.

처음 풀어 본 문제는 브론즈 2 난이도의 2798번 블랙잭 문제이다.

 

2798번: 블랙잭

 

먼저 문제를 살펴보자.

 

주어진 N장의 카드 중 3장을 골라 M 미만의 가장 큰 3장의 합을 구하면 된다.

 

입력과 출력은 다음과 같다.

 

먼저 정수 N, M을 받고, N장의 카드에 각각 어떤 수가 쓰여 있는지 주어진다.

 

 

---

문제 풀이

 

모든 경우를 탐색해 조건에 맞는 결과를 찾으면 된다고 생각했다.

친구와 함께 만나서 풀어 두 가지 풀이가 나왔다.

 

풀이 1
조합 사용

친구가 조합을 쓰면 빨리 풀겠다고 제안해 python 라이브러리를 사용해 풀어보았다.

itertools의 combinations을 사용하는 방법이다.

 

from itertools import combinations

N, M = map(int, input().split())

arr = list(map(int, input().split()))

li = list(combinations(arr, 3))

ans = 0

for i in li:
    if sum(i) <= M and sum(i) > ans:
        ans = sum(i)
        
print(ans)

분명 로컬에서 맞게 출력되는데 백준에 제출할 때 계속 런타임 에러가 났다.

런타임 에러는 프로그램이 비정상적으로 종료된 경우이다.

구글링해서 원인을 찾다가 다시 보니, 조합을 import 해 놓고서는 itertools.combinations(...)로 불러온 게 문제였다. 

 

풀이 2
반복문 중첩

전형적인 브루트포스 문제 답게 for문으로 모든 경우를 다 보는 방법이다. 

M보다 작으면서 이전 경우의 합보다 크면 ans를 대체해 결과값을 찾았다.

N, M = map(int, input().split())

arr = list(map(int, input().split()))

ans = 0

for i in range(N - 2):
    for j in range(i+1, N - 1):
        for k in range(j+1, N):
            sum = arr[i] + arr[j] + arr[k]
            if sum <= M and sum > ans:
                ans = sum

print(ans)

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

 

combinations 쓴 것 보다 for문 다중 중첩이 메모리와 시간을 덜 썼다.

오랜만에 문제 푸니까 좀 헤맸던 기억이 난다. 

매주 성실하게 풀어봐야지!