kimerikal

블랙잭

import sys


def main():
    input = sys.stdin.readline

    num_cards, threshold = map(int, input().split())
    cards = list(map(int, input().split()))

    max_score = -1

    for i in range(num_cards):
        for j in range(i + 1, num_cards):
            for k in range(j + 1, num_cards):
                score = cards[i] + cards[j] + cards[k]
                if score > threshold:
                    continue
                max_score = max(max_score, score)

    print(max_score)


main()

가능한 카드 3장 조합 전체에 대해 검사합니다. 시간복잡도는 $O(N^3)$입니다.

알고리즘 디자인 방법

프로그램이란 특정 문제를 해결하기 위해 일련의 잘 정의된 연산을 수행하는 도구이며, 알고리즘은 이 연산의 순서와 방식을 체계화한 것입니다. 이러한 알고리즘들을 다시 접근 방법과 구조에 따라 체계화한 것이 알고리즘 디자인 방법론입니다.

따라서 알고리즘 디자인 방법론을 잘 알고 있다면, 적합한 알고리즘을 빠르게 구상하여 문제를 해결하는 데 도움이 됩니다. 다음은 잘 알려진 알고리즘 디자인 방법입니다.

  • 브루트 포스
  • 재귀
  • 백트래킹
  • 동적 계획법
  • 그리디
  • 분할 정복

이 중에서 어떤 것들이 적합한지 따진 후 프로그램을 작성하면 됩니다. 첫 번째로 브루트 포스를 알아봅니다.

브루트 포스

브루트 포스 탐색법(brute-force search)은 문제에서 가능한 모든 정답 후보를 시도하는 방법입니다. 그냥 '브루트 포스'라고 짧게 부르기도 합니다.

브루트 포스의 특징은 다음과 같습니다.

  • 탐색공간(모든 후보가 포함된 집합)을 완전히 검사합니다.
  • 알고리즘의 발상, 구현, 이해가 모두 쉽고 간단합니다.
  • 보통 탐색 공간이 커질수록 효율이 크게 떨어집니다.

문제에서 탐색 공간 내의 모든 후보를 생성할 수 있고, 탐색 공간의 크기가 작으며, 각 후보를 검사하는 데 걸리는 시간이 아주 작으면 브루트 포스를 적용해 볼 수 있습니다. 위 문제의 경우에는,

  • 카드 3장 조합을 모두 만들 수 있습니다.
  • 탐색 공간의 크기는 $\binom{n}{3} = O(n^3)$이지만 $n \le 100$으로 작고, 후보마다 상수 시간 $O(1)$이 소요됩니다.

따라서 브루트 포스를 적용할 수 있습니다.

브루트 포스를 곧바로 사용하는 문제는 비교적 적지만, 발상이 쉬우므로 한번 시도해 보면 좋습니다. 일부 알고리즘 디자인 방법은 적용 후 탐색공간이 더 작아지는 경우가 있는데, 이렇게 작아진 문제에 부수적으로 브루트 포스 탐색을 사용하는 경우도 많습니다.

프로그램 실행 시간 예측

제출한 코드 실행 시간이 문제의 시간 제한보다 오래 걸리면 "틀렸습니다"를 받고 채점이 종료됩니다. 시간 제한은 C/C++ 기준으로 제시되어 있어서 Python 계열 언어에는 다음과같이 여유로운 시간 제한이 적용됩니다.

  • 일반적인 경우: 문제에서 제시한 시간 제한에 3을 곱하고 2초를 더합니다.
    • "2초"로 표시되어 있다면 $2 \times 3 + 2 = 8$초까지 허용합니다.
  • 추가 시간 없음: 문제에서 제시한 시간 제한이 그대로 적용됩니다.
    • "0.1초 (추가 시간 없음)"으로 표시되어 있다면 $0.1$초까지 허용합니다.
  • 하단 참고: 문제 아래쪽에 언어별로 시간 제한이 제시되어 있습니다.

대부분의 경우, 특히 같은 연산을 자주 반복하는 코드일수록 PyPy3가 Python3보다 빠릅니다. 메모리 사용량이 훨씬 크지만, 메모리 제한보다 시간 제한을 초과하는 경우가 많으므로 PyPy3를 기본으로 사용합니다. PyPy3는 Python3와 매우 잘 호환되므로 코드를 수정할 필요가 없습니다.

시간 제한 내로 문제를 해결하는 팁입니다.

  1. 알고리즘을 구상합니다.
  2. 문제에 주어진 변수들(N, M, K 등)을 이용하여 최악의 경우 시간 복잡도 식을 구합니다.
  3. $O()$ 안의 함수에 주어진 변수의 제한 범위를 그대로 대입합니다.
  4. Python이 1초당 대략 1억~10억 회의 기본 연산을 수행할 수 있다고 보고 시간 제한내에 들어가는지 계산합니다.
  5. 시간 제한 안에 들면 구현을 시작하고, 아니라면 다른 알고리즘을 구상하여 위 과정을 반복합니다.

예를 들어, 위 문제의 시간 복잡도 $O(n^3)$에 $n = 100$을 대입하면 $1\,000\,000$으로, 1억보다 작으니까 통과한다고 보면 됩니다.

댓글