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

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

문제

---

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

 

출력

---

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다. 

 

문제 풀이

---

백트래킹 문제.

 

사용한 재료의 개수를 1부터 N까지 전부 확인하는 백트래킹 사용 브루트포스 문제. 크기 N짜리 boolean 타입 배열을 사용하여 한 케이스에 사용하는 재료들을 저장한다. i번째 인덱스가 true라면 해당 인덱스의 재료를 사용한다는 뜻이다. 백트래킹 함수의 특정 depth에 도달하면 신 맛과 쓴 맛을 계산한다. 신 맛은 곱셈이므로 처음 초기화 시 1로 두고, 쓴 맛은 합이므로 처음 초기화 시 0으로 둔 후 boolean 타입 배열을 처음부터 확인하여 i번째 인덱스가 true라면 해당하는 맛만큼 신 맛은 곱하고 쓴 맛은 더해준다.

 

아래는 코드.

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int N;
int* sour;
int* bitter;
bool* isUsed;
int answer = 2000000000;

void backTracking(int depth, int maxDepth)
{
	if (depth == maxDepth)
	{
		int sourTaste = 1;
		int bitterTaste = 0;
		for (int i = 0; i < N; i++)
		{
			if (isUsed[i] == true)
			{
				sourTaste *= sour[i];
				bitterTaste += bitter[i];
			}
		}
		answer = min(answer, abs(sourTaste - bitterTaste));
	}
	else
	{
		for (int i = 0; i < N; i++)
		{
			if (isUsed[i] == false)
			{
				isUsed[i] = true;
				backTracking(depth + 1, maxDepth);
				isUsed[i] = false;
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N;
	sour = new int[N];
	bitter = new int[N];
	isUsed = new bool[N];
	for (int i = 0; i < N; i++)
	{
		cin >> sour[i]>>bitter[i];
		isUsed[i] = false;
	}
	for (int i = 1; i <= N; i++)
	{
		backTracking(0, i);
	}
	cout << answer << "\n";
	return 0;
}