2789. 블랙잭

2주차 알고리즘 수업 과제입니다.

“알고리즘 시간 복잡도 계산하기”

문제 링크

풀이

3가지 수를 뽑는 모든 경우의 수를 탐색해봐야 한다.

서로 다른 n개의 카드 중에서 3개의 카드를 뽑는 경우의 수는 $_nC_3$ 이다. 경우의 수가 곧 계산량 $T(n)$ 이 되므로, $O(N^3)$의 시간 복잡도를 갖게 된다.

\[\begin{align} T(n) & = {}_nC_3 \\ \\ & = \frac{n!}{3!(n-3)!} \\ \\ & = \frac{n^3-3n^2+2n}{6} \\ \end{align}\]

문제의 조건에서 카드의 개수 $N$의 범위는 $3 \leq N \leq 100$ 이다. 최악의 경우는 $N=100$ 일 때인데, 이 때의 계산량을 구해보면 $T(100) = 161700$ 으로 충분히 시간 내에 풀 수 있을 것으로 보인다.

from typing import List


def solve(N: int, M: int, C: List[int]) -> int:
    answer = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            for k in range(j+1, N):
                sum_of_cards = (C[i]+C[j]+C[k])
                if sum_of_cards <= M:
                    answer = max(answer, sum_of_cards)
    return answer


if __name__ == "__main__":
    N, M = map(int, input().split())
    C = list(map(int, input().split()))
    print(solve(N, M, C))