[백준] Bronze 2. 2798 - 블랙잭 python

문제 링크

https://www.acmicpc.net/problem/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장의 합을 출력한다.

---

제출 코드

import sys
from itertools import combinations

input = sys.stdin.readline

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

sums = [sum(nC3) for nC3 in list(combinations(cards, 3))]
sums.sort()
m_max = 0
for i in sums:
    if i > m_max and i <= m:
        m_max = i
    if i > m:
        break
print(m_max)

 

풀이

• 주어진 n개의 숫자들 중에서 3개의 카드를 뽑아 m과 비교해야 한다.
• itertools 모듈의 combinations 함수를 사용해 nC3의 조합을 구하고 sum해서 합을 sums 리스트에 더해준다.
• 순서대로 확인하기 위해 sort() 해준다.
• sums에 들어있는 숫자들을 차례로 확인해서, m보다 작으면서 기존의 숫자보다 크면 갱신해준다.
• 합이 m보다 커지면 반복문을 종료한다.

 

알아둘 사항

python에는 순열과 조합 함수가 구현되어 있다 : itertools의 permutations, combintaions

 

1. 순열 : itertools.permutations

• 순열은 순서에 상관이 있는 경우의 수
• 주어진 iterable의 모든 가능한 순열 생성함
• 기본적으로 'r' 길이의 순열 생성, 'r' 생략시 iterable의 길이와 같은 순열 생성
• 중복되는 요소 있는 iterable을 입력으로 받으면, 중복 포함한 순열 생성

import itertools

# 예시 : 리스트 [1,2,3]의 모든 순열 생성
result = itertools.prmutations([1,2,3])
print(list(result))

# 출력
> [(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)]

 

2. 조합 : itertools.combinations

• 조합은 순서에 상관이 없는 경우의 수
• 주어진 iterable에서 순서에 상관없이 'r'개의 항목을 선택하는 모든 가능한 조합 생성
• 중복되는 요소 있는 iterable을 입력으로 받으면, 중복 포함한 조합 생성

import itertools

# 예시 : 리스트 [1,2,3]에서 2개의 항목을 선택하는 모든 조합 생성
result = itertools.combinations([1,2,3], 2)
print(list(result))

# 출력
> [(1,2), (1,3), (2,3)]