[python 기초] 백준: 2798번 / itertools

📍 In a nutshell...

• brute force란, 완전 탐색을 말한다. 발생할 수 있는 모든 경우의 수를 탐색하는 방법
• itertools는 iterator를 효율적으로 만들어내는 라이브러리다

문제

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

예제 입력

5 21
5 6 7 8 9
>> 21

10 500
93 181 245 214 315 36 185 138 216 295
>>> 497 

풀이 1

만약 숫자 list가 [5,6,7,8,9]라고 가정했을 때,
5+6+7, 5+6+8, 5+8+9 > 5+7+8, 5+8+9 > 5+8+9 순으로 합을 구하고,

• 수의 합은 for문을 돌려 구한다
• M을 넘지 않는 숫자 중에서 최대값을 구한다 -> max() 이용

N,M = map(int, input().split())
card_list = list(map(int, input().split()))
result = 0

for i in range(0, N):
    for j in range(i+1, N):
        for z in range(i+1, N):
            new_num = card_list[i] + card_list[j] + card_list[z]
            
            if new_num <= M:
                result = max(result, new_num)

print(result)

풀이 2
이것보다 더 좋은 방법은 없을까 하여 찾아보니, itertools라는 라이브러리를 알게되었다.
사실 위의 방법은 별로 선호하지 않는게 for문이 3중으로 걸리기 때문.

itertools에서 combinations() 를 사용하면 더 효율적으로 구할 수 있다.

• combinations(list,n)
  • list의 요소를 가지고, 원소 개수가 n개인 조합 생성
  • 사전식 순서로 반환하며, 자료형은 tuple임
    
    

코드로 풀면 아래와 같다.

from itertools import combinations

N,M = map(int, input().split())
card_list = list(map(int, input().split()))

sum = [sum(i) for i in combinations(card_list,3) if sum(i)<=M]

print(max(sum))

출처: 백준