[python] 백준 2798 : 블랙잭

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

2798번: 블랙잭

알고리즘 분류 : 브루트 포스

---

1 : for문 중첩을 이용한 풀이(124ms)

N, M = map(int, input().split())
lst = list(map(int, input().split()))
nlst = []
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            three =  lst[i] + lst[j] + lst[k]
            if three > M:
                continue
            else:
                nlst.append(three)
print(max(nlst))

 

코드 풀이

 

첫줄에 카드 개수 N과 카드 합 한도 M을 입력 받는다.

두번째 줄에는 N개 만큼의 카드에 쓰여 있는 수를 입력 받는다.

예시

>>>5 21
>>>5 6 7 8 9

출력

21

 

5 6 7 8 9를 리스트로 입력받은 후 반복문을 중첩 사용하여 모든 경우의 수에 대한 합을 구하고 새로운 리스트에 담도록 했다.

그 합이 M을 초과한다면 그냥 반복문을 계속 진행하고, M보다 작거나 같은 경우에는 그 값을 새로운 리스트에 추가하도록 했다.

 

그리고 반복문을 완전히 빠져나왔을때 max()함수를 이용해 가장 큰 값을 출력하도록 했다.

 

---

itertools 라이브러리의 순열, 조합으로 푸는 방법

순열 : 순서를 고려하여 뽑는 경우의 수

permutations(iterable객체, r개)
iterable 객체 : 반복문, 리스트 등 반복 가능한 객체
r개 : 해당 객체에서 중복을 허용하지 않고 뽑을 개수(생략 가능)
순서대로 뽑는다.

 

import itertools

lst = ['A', 'B', 'C']
print(list(map(''.join, itertools.permutations(lst))))
print(list(map(''.join, itertools.permutations(lst, 2))))

['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
['AB', 'AC', 'BA', 'BC', 'CA', 'CB']

 

 

조합 : 순서를 생각하지 않고 뽑는 경우의 수

combinations(iterable객체, r개)
iterable 객체 : 반복문, 리스트 등 반복 가능한 객체
r개 : 해당 객체에서 중복을 허용하지 않고 뽑을 개수(생략 안됨)
뽑는 순서를 고려하지 않는다. -> (AB와 BA를 같은 것으로 본다.)

import itertools

lst = ['A', 'B', 'C']
print(list(map(''.join, itertools.combinations(lst, 2))))

['AB', 'AC', 'BC']

 

 

2 : permutations를 이용한 풀이(484ms)

from itertools import permutations

N, M = map(int, input().split())
lst = list(map(int, input().split()))
nlst = []

for three in permutations(lst, 3):
    if sum(three) > M:
        continue
    else:
        nlst.append(sum(three))
print(max(nlst))

 

3 : combinations를 이용한 풀이(156ms)

from itertools import combinations

N, M = map(int, input().split())
lst = list(map(int, input().split()))
nlst = []

for three in combinations(lst, 3):
    if sum(three) > M:
        continue
    else:
        nlst.append(sum(three))
print(max(nlst))