BOJ 2798번 : 블랙잭

안녕하세요. 지난 포스팅의 BOJ 2447번 : 별 찍기 - 10에서는 재귀함수를 이용해서 별 찍기 문제를 풀어보았습니다. 오늘은 본격적으로 새로운 알고리즘인 브루스포스 (Brute-Force; BF) 알고리즘에 대해서 설명하고 이와 관련된 문제를 풀어보도록 하겠습니다. 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 브루트포스
• combination 함수

 

제출 코드

from itertools import combinations

N, M = map(int, input().split())
numbers = map(int, input().split())
scores = sorted([M - sum(number) if M - sum(number) >= 0 else M for number in list(combinations(numbers, 3))])
print(M - scores[0])

 

해설

브루트포스는 앞으로 저희가 풀어볼 알고리즘들 중 가장 간단한 알고리즘입니다. 브루트포스를 다른 말로 하면 전수탐색이라고도 할 수 있습니다. 모든 경우의 수를 탐색해서 가장 좋은 결과를 내기 떄문에 정확도는 높지만 시간이 굉장히 오래걸리는 알고리즘이죠. 오늘은 이를 활용한 문제를 풀어보도록 하겠습니다. 브루트포스는 모든 경우의 수를 탐색해야하기 때문에 기본적으로 파이썬의 itertools 클래스에 존재하는 조합함수인 combination 메서드를 자주 사용하게 됩니다. 이를 위해 조합 (combination)과 순열 (permutation)의 차이에 대해서 설명해야겠네요. 

 

조합과 순열의 가장 큰 차이점은 순서를 신경쓰는지, 안쓰는지 입니다. 간단한 예시로 5개의 숫자 $1, 2, 3, 4, 5$에서 3개를 선택하는 조합과 순열을 생각해보면 아래와 같습니다. 

 

• 조합 : $(1, 2, 3), (1, 2, 4), (1, 2, 5), (2, 3, 4), (2, 3, 5), (3, 4, 5)$
• 순열 : $(1, 2, 3), (1, 2, 4), (1, 2, 5), (2, 1, 3), (2, 1, 4), (2, 1, 5), (3, 1, 2), (3, 1, 4), (3, 1, 5), \dots$

위와 같이 순서쌍이 중요하면 순열, 중요하지 않으면 조합이 됩니다. 오늘 저희가 볼 문제같은 경우에는 입력되는 카드 숫자의 모든 경우의 수를 확인해야하는 데 결과적으로 3개 카드의 합을 계산해야합니다. 따라서, 순서는 관계없는 조합을 사용하면 되죠. 그러므로 combination 함수를 사용하면 됩니다.

 

입력되는 카드의 숫자들 numbers 변수에서 combination 함수를 통해 해당 숫자들 중 3개를 선택하는 모든 조합을 리스트로 만들어줍니다. 이때, 어떤 조합은 저희가 목표로 만들어야하는 숫자들보다 큽니다. 이 경우에는 후보에서 제외하기 때문에 목표 숫자 $M$보다 크면 그냥 $M$으로 저장하고 작으면 $M$에서 현재 검사하는 숫자 조합의 합을 뺀 것을 저장해줍니다. 그리고 $M$에 가장 가까운 숫자 조합을 찾아야하기 때문에 해당 합들이 들어간 리스트를 정렬해주면 되죠. 그리고 $M$에서 가장 첫번째 숫자를 빼주면 $M$에 가장 가까운 숫자 조합의 합을 구할 수 있습니다. 

 

참고자료 및 그림출처

백준 코딩 문제