[백준 2960: 도영이가 만든 맛있는 음식] 파이썬 풀이 _ 조합 내장 함수 combinations

문제

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

입력

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다. 

 

 

 

---

💡풀이 방법

 

# 재료 한 개 짜리 음식
for i in ingredients:
    result = min(result, abs(i[0]-i[1]))

 

재료 한 개 짜리 음식은, 해당 재료의 쓴맛-신맛의 절댓값으로 계산

 

# 재료 2개 이상 음식
for i in range(1, n):
    combination_list = list(combinations(ingredients, i+1)) # 조합 리스트 생성
    for j in combination_list: # 조합 리스트에 대해서 곱과 합을 구함 
        sourness_multiply = 1
        bitterness_sum = 0
        for k in j:
            sourness_multiply *= k[0] # 신맛의 곱
            bitterness_sum += k[1] # 쓴맛의 합
        # 신맛의 곱 - 쓴맛의 합의 절댓값과 이전 저장값 result를 비교해서 값을 업데이트
        result = min(result, abs(sourness_multiply - bitterness_sum))

 

• 재료 2개, 3개 4개 .. 가 들어가는 음식은 조합이 필요
• combination_list 생성
• 각 combination_list에 대해 신맛의 곱과 쓴맛의 합을 저장해서 신맛의 곱 - 쓴맛의 합의 절댓값과 이전 저장값 result를 비교해서 값을 업데이트

---

combination_list?

4

1 7

2 6

3 8

4 9

입력일 때, combination_list의 예시

 

• 재료가 2개일 때 조합
• [([1, 7], [2, 6]), ([1, 7], [3, 8]), ([1, 7], [4, 9]), ([2, 6], [3, 8]), ([2, 6], [4, 9]), ([3, 8], [4, 9])]
• 재료가 3개일 때 조합
• [([1, 7], [2, 6], [3, 8]), ([1, 7], [2, 6], [4, 9]), ([1, 7], [3, 8], [4, 9]), ([2, 6], [3, 8], [4, 9])]
• 재료가 4개일 때 조합  
• [([1, 7], [2, 6], [3, 8], [4, 9])]

---

💻 전체 코드

from itertools import combinations

import sys
input = sys.stdin.readline

n = int(input()) # 요리의 개수 n
ingredients = []

for _ in range(n):
    sourness, bitterness = map(int, input().split()) #각 재료의 신맛, 쓴맛
    ingredients.append([sourness, bitterness]) # 이차원 배열 형태로 저장

result = abs(ingredients[0][0] - ingredients[0][1]) # 첫 번째 값으로 초기값 설정

# 재료 한 개 짜리 음식
for i in ingredients:
    result = min(result, abs(i[0]-i[1]))
 
# 재료 2개 이상 음식
for i in range(1, n):
    combination_list = list(combinations(ingredients, i+1)) # 조합 리스트 생성
    for j in combination_list: # 조합 리스트에 대해서 곱과 합을 구함 
        sourness_multiply = 1
        bitterness_sum = 0
        for k in j:
            sourness_multiply *= k[0] # 신맛의 곱
            bitterness_sum += k[1] # 쓴맛의 합
        # 신맛의 곱 - 쓴맛의 합의 절댓값과 이전 저장값 result를 비교해서 값을 업데이트
        result = min(result, abs(sourness_multiply - bitterness_sum))

print(result) # 결과 출력

 

---

📌 조합 내장 함수 combinations

조합을 사용하기 위해서는 combinations라는 내장 함수를 사용합니다. 이 함수는 itertools라는 파이썬 내장 패키지에 있습니다.

combinations(리스트, 조합수)

위와 같은 형태로 사용합니다. 리스트에 있는 항목들을 조합을 구하기 원하는 수를 입력하면 해당 조합을 모두 구해줍니다.

from itertoolsimport combinations

arr = ['A', 'B', 'C']
print(list(combinations(arr, 2))) # [('A', 'B'), ('A', 'C'), ('B', 'C')]

 

for문을 사용해서 구했던 조합을 내장 함수로 쉽게 구할 수 있습니다.

---

🔗 참고 링크

05. 브루트 포스