BOJ(백준) 2961[도영이가 만든 맛있는 음식]

1. 문제 설명

도영이는 여러 재료를 이용해 음식을 만들고자 합니다. 각 재료는 신맛과 쓴맛을 가지고 있습니다. 신맛은 모든 재료의 신맛의 곱으로, 쓴맛은 모든 재료의 쓴맛의 합으로 결정됩니다. 여러 재료를 섞었을 때 신맛과 쓴맛의 차이를 최소화하려고 합니다. 이때, 최소 차이를 구하는 프로그램을 작성하세요.

 

문제 URL: https://www.acmicpc.net/problem/2961

 

2. 접근법

1) 입력받기: 재료의 수와 각 재료의 신맛과 쓴맛을 입력받습니다.

2) 재귀 함수 정의: 신맛과 쓴맛을 재귀적으로 계산하여 최소 차이를 구합니다.

3) 결과 출력: 가능한 최소 차이를 출력합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# 입력값 받기: 재료의 수 N을 입력받는다.
N = int(input())
# 각 재료의 신맛과 쓴맛을 리스트로 입력받는다.
igd = [list(map(int, input().split())) for _ in range(N)]
# 결과값 초기화: 최소값을 구해야 하므로 최대값으로 초기화한다.
ans = sys.maxsize

# 재귀 함수 정의: 신맛(s)과 쓴맛(b), 현재 재료의 번호(num), 사용한 재료의 수(use)
def rec(s, b, num, use):
    global ans
    # 모든 재료를 다 사용한 경우
    if num == N:
        # 사용한 재료가 하나 이상인 경우에만 계산한다.
        if use > 0:
            # 신맛과 쓴맛의 차이 절대값을 구하여 최소값 갱신
            ans = min(ans, abs(s-b))
        return

    # 현재 재료를 사용하는 경우
    S = igd[num][0]; B = igd[num][1]
    rec(s * S, b + B, num + 1, use + 1)
    # 현재 재료를 사용하지 않는 경우
    rec(s, b, num + 1, use)

# 재귀 함수 호출: 초기값으로 신맛 1, 쓴맛 0, 첫번째 재료 번호 0, 사용한 재료 0으로 시작
rec(1, 0, 0, 0)

# 결과값 출력
print(ans)

 

4. 코드 설명

1) 입력값 받기

- 재료의 수와 각 재료의 신맛과 쓴맛을 입력받습니다.

2) 재귀 함수 정의

- 재귀 함수를 정의하여 모든 재료를 사용했을 때의 신맛과 쓴맛의 차이를 계산하고 최소값을 갱신합니다.

3) 재귀 함수 호출

- 재귀 함수를 초기값으로 호출하여 계산을 시작합니다.

4) 결과값 출력

- 최종적으로 계산된 최소값을 출력합니다.

 

***

이 코드는 모든 재료 조합을 탐색하여 신맛과 쓴맛의 차이가 최소가 되는 값을 구하는 문제를 해결합니다. rec 함수는 재귀적으로 모든 조합을 시도하며, 재료를 사용하는 경우와 사용하지 않는 경우로 나누어 탐색합니다. 최종적으로 신맛과 쓴맛의 차이의 최소값을 ans에 저장하고, 이를 출력합니다.

***

5. Github으로 확인

coTest/BOJ/BOJ01_05_01_2961.py at main · pcy4196/coTest