백준 - 2961 도영이가 만든 맛있는 음식 [백트래킹]

 

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

 

1. 문제 요약

재료의 개수 N, 그 재료의 맛 S, B가 주어진다.

S는 곱, B는 덧셈으로 맛이 변한다.

재료를 적절하게 조합하여 S와 B의 차가 가장 작은 경우의 맛을 출력하라.

 

2. 접근 방법

• 재귀함수를 이용하여 조합을 구해줍니다.
• 재료를 사용하거나, 사용하지 않거나로 구분하여 진행합니다.

 

3. 파이썬

from sys import stdin
input = stdin.readline

def solution(depth:int, used:int, S:int, B:int):
    if depth == N:
        if used != 0:
            results.append(abs(S-B))
        return
    # 사용하거나
    solution(depth+1, used+1, S*SB[depth][0], B+SB[depth][1])
    # 사용하지 않거나
    solution(depth+1, used, S, B)

N = int(input())
SB = [list(map(int, input().split())) for _ in range(N)]
results = []

solution(0,0,1,0)
print(min(results))

 

4. 자바

static int[][] ingredients;
static int answer = Integer.MAX_VALUE;

static private void recursive(int index, int sour, int bitter, int use) {
    if (index == ingredients.length) {
        if (use == 0) {
            return;
        }
        answer = Math.min(answer, Math.abs(sour - bitter));
        return;
    }

    recursive(index + 1, sour * ingredients[index][0], bitter + ingredients[index][1], use + 1);
    recursive(index + 1, sour, bitter, use);
}

recursive(0, 1, 0, 0);

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/2961.%E2%80%85%EB%8F%84%EC%98%81%EC%9D%B4%EA%B0%80%E2%80%85%EB%A7%8C%EB%93%A0%E2%80%85%EB%A7%9B%EC%9E%88%EB%8A%94%E2%80%85%EC%9D%8C%EC%8B%9D