[백준] 2798 블랙잭 (파이썬/python)

🎈문제

https://www.acmicpc.net/problem/2798

 

🎁어떤 알고리즘?

1. M을 넘지 않으면서 M에 최대한 가까운 카드를 3장의 합을 알려면 모든 경우의 수를 다 따져봐야한다.

2. 모든 경우의 수를 다 따져보는 알고리즘 기법을 부르트포스 알고리즘이라고 하는데, 거창한거 없이 그냥 파이썬 내장 라이브러리를 사용하면 된다.

3. 이 문제의 경우, 3장의 "합"을 구하므로 카드의 순서는 신경쓰지 않아도 된다.

4. 따라서 conbination(조합)으로 카드 3장을 구하면 된다.

💻코드

from itertools import combinations

N,M = map(int,input().split())
card = list(map(int,input().split()))
temp = 0

card_com = list(map(sum,combinations(card,3)))
for i in card_com:
  if i <= M and i > temp:
    temp = i

print(temp)

 

❓ 경우의 수 ( 순열 / 조합 / 중복 순열 / 중복 조합)

- 순열 : 순서를 고려하여 뽑는 경우의 수(중복 x)

from itertools import permutations

a = [1,2,3]

print(list(permutations(a,2)))

#print
[(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]

- 조합 : 순서를 고려하지 않고 뽑는 경우의 수(중복 x)

from itertools import combinations

a = [1,2,3]
print(list(combinations(a,2)))

#print
[(1,2), (1,3), (2,3)]

- 중복 순열 : 뽑은 순서를 고려하되, 주머니에 뽑은 구슬을 다시 집어넣어 중복이 가능하게 뽑는 경우의 수(중복 o)

from itertools import product

a = [1,2,3]

print(list(product(a,2)))

#print
[(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]

 

- 중복 조합 : 순서를 고려하지 않고 주머니에 뽑은 구슬을 다시 집어넣어 중복이 가능하게 구슬을 뽑는 경우의 수(중복 o)

from itertools import combinations_with_replacement
a = [1,2,3]

print(list(combinations_with_replacement(a,2)))

#print
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]