[백준 2798번-파이썬/Python] 블랙잭

http://acmicpc.net/problem/2798

 

{코드}

n, t = map(int, input().split())
data = tuple(map(int, input().split()))
def blackjack():
	ans = 0
	for i in data[:-2]:
		for j in data[1:-1]:
			if i == j:
				continue
			for k in data[2:]:
				if j == k or i == k or i+j+k > t:
					continue
				if i+j+k == t:
					return t
				else:
					ans = max(ans, i+j+k)
	return ans
print(blackjack())

{설명}

브루트 포스는 결국 모든 경우의 수를 전부 시도해보는 방법입니다.

그래서 3장의 카드를 고르기 위해 반복문 세 개를 사용하는데 만약 합이 원하는 결과보다 크면 continue, 같으면 합 반환, 작으면 현재 저장된 값이랑 비교하여 더 큰 값을 저장합니다.

만약 원하는 결과가 21이면 22일때는 continue, 21일 때는 21 반환, 19일 때는 현재 저장된 값이 20이면 계속 20을 저장하고 18이면 19를 저장합니다.

그리고 중복해서 카드를 뽑는 일이 없도록 만약 두 값이 같으면 continue를 해주었는데 인덱스로 비교하지 않았음에도 정답인 것을 보면 카드 사이에도 중복은 없는 것으로 보입니다.(아닐 수도 있습니다.)

{코드}

from itertools import combinations
n, m = map(int, input().split())
data = list(map(int, input().split()))
ans = 0
for order in combinations(data, 3):
  s = sum(order)
  if s == m:
    ans = s
    break
  elif ans < s < m:
    ans = s
print(ans)

{설명}

위 방법 외에도 조합을 이용할 수 있습니다.

조합은 주어진 배열에서 n개를 순서에 구애받지 않고 뽑는 것입니다.

만약 [1, 2, 3, 4, 5]에서 3개를 뽑을 때 [1, 3, 5], [5, 1, 3], [1, 5, 3]등은 모두 같은 것으로 간주하는 것입니다.

그렇기에 카드 덱에서 n개를 뽑을 때 나올 수 있는 모든 결과를 반복하며 만약 합이 원하는 결과면 break, 아니면 현재 저장하는 값보다 크고 원하는 결과보다 작을 때 ans를 업데이트합니다.

*조합은 파이썬의 내장 라이브러리인 itertools의 combinations를 통해 사용할 수 있으며 첫 번째 인자로 이터러블을, 두 번째 인자로 개수를 지정합니다.

**조합을 사용할 경우 실행 시간이 단축됩니다. 이유는 따로 combinations의 구현방법을 살펴보시기 바랍니다.