개발일지/Algorithm
백준 - 2961 도영이가 만든 맛있는 음식 [백트래킹]
E-room
2023. 10. 6. 16:28
728x90
2961번: 도영이가 만든 맛있는 음식
첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은
www.acmicpc.net
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. 전체 코드
728x90