백준 2961 도영이가 맛있는 음식 / python

문제 : 2961

풀이 point

N의 범위가 10으로 매우 작다. 모든 조합을 구하기에 시간이 부족하지 않으므로 백트래킹 기법을 활용하여 모든 조합을 구한 뒤 쓴맛과 신맛의 차이를 구한다.

풀이 코드

def back(depth, n, start, visit):
  global ans
  if depth == n:
    S, B = 1, 0
    for i in range(N):
      if visit[i]:
        S *= ingre[i][0]
        B += ingre[i][1]
    ans = min(ans, abs(S-B))
    return
  for i in range(start, N):
    if visit[i]:
      continue
    visit[i] = True
    back(depth+1, n, i+1, visit)
    visit[i] = False

N = int(input())

ingre = [list(map(int, input().split())) for _ in range(N)]
ans = int(1e9)

for i in range(1, N+1):
  visit = [False]*(N)
  back(0, i, 0, visit)
print(ans)