파이썬 알고리즘 214번 | [백준 2961번] 도영이의 요리 - 백트래킹

214. 도영이의 요리

1) 어떤 전략(알고리즘)으로 해결?

백트래킹, 조합

2) 코딩 설명

조합 활용

<내 풀이>

from itertools import combinations
import sys
n = int(sys.stdin.readline().rstrip()); lis=[]
for i in range(n) : 
    sour, bit = map(int, sys.stdin.readline().rstrip().split())
    lis.append((sour, bit))
    
# 도영이는 재료를 적절히 섞어서 
# 요리의 신맛과 쓴맛의 차이를 작게 만들기
# 재료 1개부터 n개 고를 수 있지
cusine_differ_sour_bitter_min = 10000000001
for i in range(1,n+1) :
    comb = combinations(lis, i)
    
    for c in comb :  # 한요리 
        #print(c)
        sour=1; bitter=0
        for x,y in c :
            sour*=x
            bitter+=y
        if abs(bitter-sour)<cusine_differ_sour_bitter_min:
            cusine_differ_sour_bitter_min=abs(bitter-sour)

print((cusine_differ_sour_bitter_min))

<내 틀렸던 풀이, 문제점>

23 % 서 틀림

from itertools import combinations
import sys
n = int(sys.stdin.readline().rstrip()); lis=[]
for i in range(n) : 
    sour, bit = map(int, sys.stdin.readline().rstrip().split())
    lis.append((sour, bit))
    
# 도영이는 재료를 적절히 섞어서 
# 요리의 신맛과 쓴맛의 차이를 작게 만들기
# 재료 1개부터 n개 고를 수 있지
cusine_differ_sour_bitter_min = 1000000001
for i in range(1,n+1) :
    comb = combinations(lis, i)
    
    for c in comb : 
        #print(c)
        sour=1; bitter=0
        for x,y in c :
            sour*=x
            bitter+=y
        if abs(bitter-sour)<cusine_differ_sour_bitter_min:
            cusine_differ_sour_bitter_min=bitter-sour # 이 부분에서 abs 로 저장해줬어야 하는데 (차이를 저장하기 위해서) 그냥 저장해서 틀린 것 

print(abs(cusine_differ_sour_bitter_min))

• 왜냐면 가장 신 맛과 쓴 맛 차이가 적은 요리 를 저장하는 수에 절댓값으로 저장안하고 그냥 저장했더니 에러가 난 것이지!

<반성 점>

<배운 점>