BOJ2789 - 블랙잭 (python3)

오늘의 문제는 부르트 포스 단계 첫번째 문제인 블랙잭.

예시 입출력은 잘 나오는데 뭐가 문제인거지 싶어서 고민하다 4트만에 성공

내가 간과한 것 :

세 카드의 숫자를 더한 값이 M을 넘으면 안된다

이것을 중점적으로 수정하니 풀 수 있었다~

import sys

n, m = map(int,sys.stdin.readline().rstrip('\n').split())
cards_list = list(map(int,sys.stdin.readline().rstrip('\n').split()))
gap = 300000
close_total = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if m-(cards_list[i]+cards_list[j]+cards_list[k])>=0 and abs(m-(cards_list[i]+cards_list[j]+cards_list[k]))<gap:
                gap = abs(m - (cards_list[i] + cards_list[j] + cards_list[k]))
                close_total = cards_list[i] + cards_list[j] + cards_list[k]
print(close_total)

모든 경우의 수를 계산한다는 점에서 그닥 효율적인 알고리즘은 아닌 것 같다. 근데 계산안해보면 또 모르는거라...필요한 과정이라고 생각한다.

여기에서 조금 더 효율을 챙긴다면 gap이 0이 되면 그냥 프로그램을 끝내도록 하는 것을 추가하기..?

근데 답이 맨 마지막에 있는 경우도 있기 때문에 어쨌든 효율은 O(n^3)이다..