[백준/2961] 도영이가 만든 음식 | 브루트포스의 구조(조합) | 곱셈 누적 초기화는 1 | 디버깅을 열심히 하자. 내가 짠 코드를 파악하는 방법

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))

---

알게된 점

이번에 처음 코테를 치면서 느낀 것은 모르겠더라도 끝까지 작성을 해보고, 로직을 짜보는 과정은 반드시 거쳐야 한다는 거다. 이때 시간낭비를 하지 않게 적절히 잘 조절하는 게 중요한데, 일단 30분 정도의 시간을 재고 그 시간 동안에는 끊임없이 사고를 하는 게 코드를 구현하는 힘을 기르는 데에 많은 도움이 된다. 그래서 이 문제를 풀 때도 혼자서 끝까지 풀어보려고 노력했다. 그랬더니 못할 것같았지만 고민해서 낸 로직이 잘 구현되었고, combination 함수에 대한 이해도 깊어졌다! 

 

마지막 최소값을 구할 때 "같은 요리일 때"를 생각 못해서 😂 이 부분을 학회 멘토님께 여쭤봤지만, 그래도 로직을 잘 구현했으니 앞으로 이런식으로 알고리즘을 연습해나가면 코테에서도 충분히 승리를 거둘 수 있을 것이다.

 

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