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

👉 문제링크

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

---

---

🔸 문제 분석 🔸

• 재료 선택에 따라 신맛과 쓴맛의 합이 변한다.
  • 신맛(s)은 곱으로 계산한다.
  • 쓴맛(b)은 합으로 계산한다.
• 신맛과 쓴맛의 차이의 최소값을 출력한다.

🔸 코드 🔸

n = int(input())

taste = []
visit = [0] * n
answer = 1000000000

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

def dfs(d, m, s, b, x):
    global answer
    if d >= m:
        if s > b:
            sum = s - b
        else:
            sum = b - s
        answer = min(answer, sum)
        return
    
    for i in range(x,n):
        if visit[i] == 0:
            visit[i] = 1
            dfs(d+1, m, s*taste[i][0], b+taste[i][1], i)
            visit[i] = 0

for i in range(1, n+1):
    dfs(0, i, 1, 0, 0)

print(answer)

🔸 코드 해석 🔸

• answer의 초기값은 문제에서 주어진 맛의 범위(10억)로 선택했다.
• 재귀를 이용하여 모든 경우의 수를 탐색하고 최소값을 계산한다.
  • dfs의 깊이제한을 선택할 재료의 수로 생각하고 탐색한다.
  • 1개부터 n개의 선택을 모두 탐색한다.
• 쓴맛 s는 곱으로 계산하므로 초기값을 1로 시작한다.

---

🔸 end 🔸

• 처음 풀어봤다면 어려울 수도 있었을 것 같은데, BOJ_14620 : 꽃길 문제에서 사용한 풀이로 간단히 풀 수 있었다.
• 비트마스킹으로도 풀 수 있는 것 같다. 아마 1차원 리스트안에서 재귀로 탐색했으니, 비슷하게 반복문으로 탐색하는 것 같다.
• 답안 제출을 확인해보니 이상한 모듈이 import 되어있어서 삭제하고 다시 제출했다.