[2961/python] 도영이가 만든 맛있는 음식

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

2961번: 도영이가 만든 맛있는 음식

알고리즘

 완전탐색 문제다. 문제에서 "요리의 쓴맛과 신맛은 모두 1,000,000,000보다 작은 양의 정수라고 했기 때문에 브루트포스임을 단번에 파악할 수 있었다.

신맛과 단맛을 저장해서 선택하여 곱과 합을 조합해줘야 하기 때문에 combination 함수를 사용했다. 브루트포스 알고리즘은 조건을 빼먹지 않고 구현하는 것이 핵심이기 때문에, 하나하나 구체적으로 코드를 작성하다보니 다소 길어졌다. 다른 분들의 코드를 봤을 때는 이중리스트로 구현을 하셨는데, combination을 이중 리스트에 적용하는 방법을 몰라서 이렇게 풀었다. 또한, 문제에서 한 가지 재료는 반드시 들어가야한다고 조건을 주었으므로 combination 함수의 적용 범위를 for문으로 조정해주었다.

---

최종코드

from itertools import combinations as comb
n = int(input())
s_total, b_total = [], []
s_combi, b_combi = [], []
ans = []

for _ in range(n) : 
    s, b = map(int, input().split())
    if n == 1 : print(abs(s-b)); exit()
    else: 
        s_total.append(s)
        b_total.append(b)
        
# 신맛의 조합
for i in range(1, n+1) : 
    for s_item in comb(s_total, i) : 
        S = 1
        for j in s_item : 
            S *= j
        s_combi.append(S)
                
# 쓴 맛의 조합   
    for b_item in comb(b_total, i) : 
        B = sum(b_item)
        b_combi.append(B)  

for i in range(len(s_combi)) : 
    ans.append(abs(s_combi[i]-b_combi[i]))
        
print(min(ans))

---

알게된 점

• 곱셈을 누적할 때에는 1로 초기화한다.(되게 기본적인 것같지만,, 이걸 놓쳐서 계속 0을 출력했었다.)
• print로 디버깅을 여기저기 해보면서 내가 짠 코드가 어떻게 굴러가는지 파악할 것.(귀찮아도 계속 해봐야한다.)
• c = list(comb(range(1,4),i) 이렇게 한줄로 써서 조합들을 리스트에 저장하는 방법