[백준 - Python] 2798. 블랙잭 (완전 탐색)

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

2798번: 블랙잭

 

코드 및 설명

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

total = 0
result = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            total = card[i] + card[j] + card[k]
            if total <= m:
                result = max(total, result)

print(result)

 

N이 최대 100까지만 가능하기 때문에

3중 반복문으로 완전 탐색을 해도

시간 제한에 걸리지 않음을 확인할 수 있다.

 

처음에 푼 풀이는 반복문을 돌릴 때,

for i in card:
    for j in card:
        for k in card:
            if i != j and j != k and i != k:
                total = i + j + k

 

위와 같이 같은 인덱스인 경우도 전부 돌면서

조건문으로 확인을 계속 해주었다.

 

해당 방식보다는 인덱스를 같은 경우가 안 생기게

조정해 주는 방식이 더 빨랐다. (당연히;;)

 

생각이나 고민을 더 해서 코드를 효율적으로 짜는 연습을 해야 한다.

 

 

itertools 라이브러리의 combinations 조합을 활용하는 방식도 기억해두면 유용할 것 같다.

from itertools import combinations

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

result = 0
for card in combinations(cards, 3):
    tmpSum = sum(card)
    if tmpSum <= m:
        result = max(result, tmpSum)

print(result)

 

막간 복습을 하자면,

permutations(iter, r)
product(*iter, repeat = 1)

combinations(iter, r)
combinations_with_replacement(iter, r)

 

위에서부터, 순열/중복순열, 조합/중복조합 이다.

 

4가지 경우 모두 iterable 객체와

뽑아낼 개수 r을 인자로 받고

각자의 고유 클래스로 반환값이 나오기 때문에

전체 출력을 하고 싶다면 list() 함수를 이용해 리스트화 해준 다음에 출력을 해준다.

 

반환되는 값 자체가 iterable하기 때문에

반복문에서 바로 순회 객체로 사용 가능하다.

 

각각의 순회 요소는 튜플이고

순회 요소의 요소들이 정수형인 경우 sum 함수를 통해 전체 합을 쉽게 구할 수 있다.

 

 

약간 활용법이 다른 함수는 중복 순열 함수인데,

하나의 iterable을 통해

product(iterable, repeat = 2)

 

다음과 같이 단순히 중복순열을 구할 수도 있지만,

 

실제적으로 해당 함수는

이름에서 추측할 수 있듯이

여러 iterable의 데카르트곱을 반환한다.

 

예시로 확인해보자.

from itertools import product

iter1 = ['A', 'B', 'C']
iter2 = [1, 2, 3]

for i in product(iter1, iter2, repeat = 1):
    print(i)

 

위의 코드를 실행하면,

('A', 1)
('A', 2)
('A', 3)
('B', 1)
('B', 2)
('B', 3)
('C', 1)
('C', 2)
('C', 3) 와 같은 결과가 출력된다.