백준 2798번(Python) : 블랙잭

www.acmicpc.net/problem/2798

2798번: 블랙잭

딜러가 외치는 m보다 작은 최대합을 구하는 문제이다. 배열안에서 세 개의 수를 골라 합을 구하면 되므로 for문을 3개사용해서 답을 구했다. 아무래도 for문이 3개 쓰이다 보니 시간복잡도가 커서 틀릴 줄 알았는데.. 맞았다..!? 

 

import sys
input = sys.stdin.readline

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

sum = 0
result_arr = []
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            sum = arr[i] + arr[j] + arr[k]
            if sum <= m:
                result_arr.append(sum)

print(max(result_arr))

 

+ 이보다 좋은 방법이 있을까 싶어 한.. 8개정도 블로그를 찾아봤는데 대부분 이렇게 for문을 3개 사용해서 푼 것같다. 가장 간단한 방법이며 시간복잡도에도 걸리지 않기때문에 다들 이렇게 사용하는것 같다.