[백준/BOJ] 백준 2961번 : 도영이가 만든 맛있는 음식

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

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

재료의 번호를 0번부터 n-1번까지로 했다. 현재 selected의 재료를 골랐고, choice번(0~n-1번) 재료의 선택 판단을 할 때 신맛과 쓴맛의 가장 작은 차이를 구하는 함수를 만들었다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdlib>
using namespace std;

int n;
vector<pair<int, int>> taste;

//현재 selected의 재료를 골랐고, choice번(0~n-1번) 재료의 선택 판단을 할때
//신맛과 쓴맛의 가장 작은 차이를 구한다
int Solve(vector<pair<int, int>>& selected, int choice)
{
	int ret = 1000000000;

	//0~n-1번 재료까지 있으므로 이때는 모든 재료의 선택여부를 정했을때이다.
	if (choice == n)
	{
		//재료를 하나도 선택하지 않았을때
		if (selected.size() == 0)
			return 1000000000;

		int s_taste = 1;
		int b_taste = 0;

		for (int i = 0; i < selected.size(); i++)
		{
			s_taste *= selected[i].first;
			b_taste += selected[i].second;
		}

		return abs(s_taste - b_taste);
	}

	//choice번 재료를 선택하지 않을때
	ret = min(ret, Solve(selected, choice + 1));

	//choice번 재료를 선택할때
	selected.push_back(taste[choice]);
	ret = min(ret, Solve(selected, choice + 1));
	selected.pop_back();

	return ret;
}

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

	int s, b;
	vector<pair<int, int>> selected;

	cin >> n;

	//재료의 번호를 0번부터 n-1번까지로 했다
	for (int i = 0; i < n; i++)
	{
		cin >> s >> b;
		taste.push_back(make_pair(s, b));
	}

	cout << Solve(selected, 0);

	return 0;
}