📌문제
카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 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장의 합을 출력한다.
💡Idea
카드 3장을 뽑을 수 있는 모든 경우의 수를 따져보는 완전 탐색(Brute-force) 문제입니다.
M보다 큰 값을 가지는 카드는 제외하는 등의 조건을 줄 수도 있지만, 카드의 개수가 최대 100개로 그렇게 크지 않기 때문에 조건 없이 모든 경우의 수를 따져보는 것으로 문제를 해결해보았습니다!
💻코드1
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
card_list = input().split()
card_list = [int(x) for x in card_list]
answer = 0
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
sum = card_list[i] + card_list[j] + card_list[k]
# 카드 3개의 합이 m보다 크지 않고, 현재 가장 최대 값을 가지는 answer보다 크다면, answer에 새로운 합을 넣어준다.
if sum <= m and sum > answer:
answer = sum
print(answer)📂 메모리
- 30840 KB
⏰ 시간
- 120 ms
📝코드1 설명
삼중 for문을 통해서 카드 3개를 뽑는 조합을 모두 고려할 수 있습니다.
예를 들어, 5,6,7,8,9 의 카드가 있다고 가정해보겠습니다.
5개의 카드 조합을 만들기 위해서 우리는 5/6/7, 5/6/8, 5/6/9, 5/7/8, 5/7/9, 5/8/9...의 순서대로 조합을 만들 수 있습니다.
즉, 첫 번째 카드를 선택하면 두 번째 카드는 첫 번째 카드 다음부터 선택을 하고, 세 번째 카드는 두 번째 카드 다음부터 선택을 하는 것입니다.
따라서 첫 번째 for문의 변수가 i라면, 두 번째 for문의 변수인 j는 0이 아닌 i+1부터 시작을 하고, 세 번째 for문의 변수인 k 역시 0이 아닌 j+1부터 시작을 하도록 합니다.
그리고, 만들어진 조합의 합이 m보다 작으면서 현재까지 나온 합 중 가장 큰 값보다는 크다면 그 합을 answer변수에 넣어줍니다.
최종적으로 나온 answer 변수의 값이 m보다 크지 않으면서 m에 가장 가까운 합이 됩니다.
변수
n: 카드의 개수m: 이보다 크지 않으면서 가장 가까워야 하는 숫자card_list: 카드 리스트answer:m보다 크지 않으면서 가장 가까운 세 카드의 합
💻코드2
import sys
from itertools import combinations
input = sys.stdin.readline
n, m = map(int, input().split())
card_list = input().split()
card_list = [int(x) for x in card_list]
answer = 0
for x in list(combinations(card_list, 3)):
sum_value = sum(x)
if sum_value <= m and sum_value > answer:
answer = sum_value
print(answer)
# 위의 for문을 아래와 같이 선언형으로도 해결할 수 있다.
# sum_list = list(filter(lambda x: x <= m, [sum(x) for x in list(combinations(card_list, 3))]))
# sum_list.sort(reverse=True)
#print(sum_list[0])📂 메모리
- 41464 KB
⏰ 시간
- 132 ms
📝코드2 설명
파이썬에서 제공하는 순열조합 라이브러리 itertools의 combinations를 사용해보았습니다. 해당 함수를 사용하면 리스트의 조합을 쉽게 구할 수 있다는 장점이 있습니다.
코드 1과 마찬가지로, 선택된 3개 카드의 합이 m보다 크지 않고, 현재 가장 큰 합보다 크다면 answer에 해당 값을 넣어줍니다.
📍 정렬을 해야하지만, 선언형이 좋다면 주석과 같이 작성해도 문제를 풀 수 있다. 다만 메모리와 시간이 조금씩 더 늘어나기는 합니다.
변수
n: 카드의 개수m: 이보다 크지 않으면서 가장 가까워야 하는 숫자card_list: 카드 리스트answer:m보다 크지 않으면서 가장 가까운 세 카드의 합sum_list: 모든 3개 카드 조합의 합 중m보다 크지 않은 수들의 리스트
