[파이썬/Python] 백준 2798번 블랙잭

[파이썬/Python] 백준 2798번 블랙잭

2798번: 블랙잭

---

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

예제 입력 1

5 21
5 6 7 8 9

예제 출력 1

21

예제 입력 2

10 500
93 181 245 214 315 36 185 138 216 295

예제 출력 2

497

풀이

import sys
input = sys.stdin.readline

# 입력 받기
n, m = map(int, input().split())   # n: 카드의 개수, m: 최대 합
cards = sorted(list(map(int, input().split())), reverse=True)   # 카드 리스트를 내림차순 정렬

# 결과 값 초기화
res = 0   # 카드 3장의 합 중 M에 최대한 가까운 값

# 카드 3장 선택
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            score = cards[i] + cards[j] + cards[k]   # 3장의 합 구하기
            if score <= m:   # 3장의 합이 M을 넘지 않으면
                res = max(res, score)   # 현재까지 구한 카드 3장의 합 중 M에 최대한 가까운 값 저장
                break   # 현재 i,j,k를 사용하는 반복문 종료 (남은 k값에 대해서는 확인할 필요가 없음)

# 결과 출력                
print(res)

3장의 카드를 선택하는데, 첫번째 for문은 가장 큰 카드부터 시작하여, 두번째 for문은 그 다음으로 큰 카드부터, 세번째 for문은 세번째로 큰 카드부터 선택하도록 구현되어 있다.

반복문의 범위를 위와 같이 설정한 이유는 cards 리스트를 내림차순으로 정렬한 것과 연관이 있다.

cards 리스트를 sorted() 함수로 내림차순으로 정렬한 이유는 카드 중 가장 큰 수를 먼저 선택할 수 있도록 하기 위해서이다. 그리고 이를 위해서 range() 함수에도 반대로 범위를 지정한다.

예를 들어, n=5일 때 cards 리스트가 [3, 2, 5, 8, 1]이라면 내림차순으로 정렬한 [8, 5, 3, 2, 1] 순서대로 카드를 선택하면 가장 큰 수부터 3장을 선택할 수 있다. 그러므로 첫 번째 for 문에서 range(n-2)은 0, 1, 2가 된다. 이는 cards 리스트에서 가장 큰 수 8, 그 다음으로 큰 수 5, 그리고 세 번째로 큰 수 3을 선택할 수 있는 경우의 수이다. 그리고 첫 번째 선택한 카드가 8일 경우, 두 번째 for 문에서 range(i+1, n-1)은 1, 2, 3이 된다. 이는 cards 리스트에서 두 번째로 큰 수 5, 그 다음으로 큰 수 3, 그리고 가장 작은 수 1을 선택할 수 있는 경우의 수이다. 따라서 이렇게 range 함수의 인자를 조절함으로써 각 단계에서 선택할 수 있는 카드 조합의 범위를 지정할 수 있다.

위 코드에서는 반복문 안에서 세 카드의 합이 M을 넘지 않는 가장 큰 값을 찾기 위해, 삼중 for문과 break문을 사용한다. 이때, 각 for문은 range를 사용하여 반복 횟수를 지정한다.

세 개의 카드를 선택하는 for문에서는 i, j, k 변수를 사용하여 각각 카드의 인덱스를 지정하고, range(n-2), range(i+1, n-1), range(j+1, n)를 사용하여 인덱스 범위를 지정한다. 이때, range(n-2)는 n-2번까지의 인덱스 범위를 의미하며, range(i+1, n-1)은 i+1부터 n-1까지의 인덱스 범위를 의미한다. 즉, i보다 큰 인덱스 범위를 지정하는 것이다.

이 코드에서 sorted(reverse=True)를 사용하여 카드 리스트를 내림차순으로 정렬했다. 이를 통해, 카드 리스트의 앞쪽에 있는 카드부터 큰 값을 가지게 된다. 이렇게 큰 값을 가진 카드부터 선택해가면서, 가장 큰 합을 찾아나가는 것이다.

이때, 각 카드를 선택한 후에는, 선택된 카드의 합이 M을 넘지 않는지 확인한다. 합이 M을 넘지 않는 경우에는, res = max(res, score)를 사용하여 최대 합을 계속해서 업데이트해 나가고, break문을 사용하여 이후의 반복을 중단한다. 이를 통해, M에 최대한 가까운 카드의 합을 찾아내게 된다.

위 코드의 시간 복잡도는 O(n^3)이다.

세 개의 반복문이 중첩되어 있기 때문에, 최악의 경우 입력값 n이 매우 커질 경우 실행 시간이 급격히 증가할 수 있다.

첫 번째 반복문은 0부터 n-3까지 실행되며, 두 번째 반복문은 첫 번째 반복문 이후부터 n-2까지 실행된다. 세 번째 반복문은 두 번째 반복문 이후부터 n-1까지 실행된다. 따라서, 총 실행 횟수는 n(n-1)(n-2)/6 으로 계산된다. 이는 대략 O(n^3)에 해당한다.

하지만 위 코드는 세 개의 카드를 선택한 결과 중에서 최대값을 찾기 때문에, 불필요한 반복을 줄일 수 있다. 예를 들어, 3장의 카드를 선택했을 때 그 합이 M을 초과한다면, 세 번째 반복문은 더 이상 실행할 필요가 없습니다. 이를 반영하여 코드를 최적화할 경우, 시간 복잡도를 줄일 수 있다.

참고자료

로그인