[백준/Python] 2961번: 도영이가 만든 맛있는 음식

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

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

---

 

---

문제 분석

N개의 재료 중 몇 가지의 재료를 골라 음식을 만든다.

음식을 만들 때 재료의 신맛과 쓴맛이 정해지는데, 신맛은 사용한 재료의 신맛의 곱이고 쓴맛은 합이다.

 

N개의 재료 중 몇 가지 재료를 고르는 방법은 N의 길이를 가진 집합의 부분 집합을 구하는 것이다.

단순 반복을 통해 파이썬 라이브러리인 combinations를 구하면 쉽게 구할 수 있겠지만 백트래킹 알고리즘 사용법을 익히는 것이 좋기 때문에 백트래킹을 통해 문제를 풀기로 하였다.

 

단순하게 생각했을 때, 음식을 만드는 경우 재료를 사용하거나 사용하지 않거나 둘 중 하나이다.

이러한 사실을 통해 visited라는 배열을 재료의 개수만큼 0으로 초기화시켜 선언해 주고 재료를 사용했다면 1로 바꾸어주면 된다.

 

def makeFood(idx):
    global answer

    if idx == len(material):
        cnt, s, b = 0, 1, 0

        for i in range(len(visited)):
            if visited[i]:
                cnt += 1
                s *= material[i][0]
                b += material[i][1]

        if cnt == 0:
            return

        answer = min(answer, abs(s - b))
        return answer

    visited[idx] = 1
    makeFood(idx + 1)
    visited[idx] = 0
    makeFood(idx + 1)

사용한 재료의 개수를 판단하기 위해 cnt라는 변수를 선언하고, 신맛을 계산하기 위해 s는 1로, 쓴맛을 계산하기 위해 b는 0으로 선언한다.

 

백트래킹 알고리즘

1. 재료를 사용할 때

visited[idx]를 1로 바꾸어주고 다음 인덱스로 넘어가 함수를 실행한다.

 

2. 재료를 사용하지 않을 때

visited[idx]를 0으로 바꿔주고 다음 인덱스로 넘어가 함수를 실행한다.

 

그 후 idx가 len(재료의 배열)(== 재료의 종류 + 1)가 된다면,

모든 재료가 사용하는지, 사용하지 않는지 판단이 되었으므로 신맛과 쓴맛의 계산을 진행한다.

 

재료를 사용했다면 사용한 재료의 수를 하나 증가시키고

신맛은 재료의 신맛을 곱하고, 쓴맛은 재료의 쓴맛을 더한다.

 

문제에서 재료는 무조건 하나 이상 사용해야 하기 때문에 cnt가 0이라면 바로 return 하여 함수를 종료해줘야 한다.

 

---

코드

import sys

INF = sys.maxsize

n = int(input())

material = []

for _ in range(n):
    material.append(list(map(int, input().split())))

visited = [0 for _ in range(n)]
answer = INF


def makeFood(idx):
    global answer

    if idx == len(material):
        cnt, s, b = 0, 1, 0

        for i in range(len(visited)):
            if visited[i]:
                cnt += 1
                s *= material[i][0]
                b += material[i][1]

        if cnt == 0:
            return

        answer = min(answer, abs(s - b))
        return answer

    visited[idx] = 1
    makeFood(idx + 1)
    visited[idx] = 0
    makeFood(idx + 1)


makeFood(0)

print(answer)