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

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

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

 

문제

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

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

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

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

 

입력

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

출력

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

---

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

int ans = 2000000000;
int N, S, B;
vector<pair<int, int>> food;

int dfs(int s_idx, vector<int> v)
{
	int a = 1, b = 0;
	for (int elm : v)
	{
		a *= food[elm].first;
		b += food[elm].second;
	}
	ans = (abs(a - b) <= ans ? abs(a - b) : ans);
	
	for (int i = s_idx+1; i < N; i++)
	{
		v.push_back(i);
		dfs(i, v);
		v.pop_back();
	}

	return 0;
}

int main() {

	cin >> N;
	
	for (int i = 0; i < N; i++)
	{
		cin >> S >> B;
		food.push_back(make_pair(S, B));
	}

	for (int n = 0; n < N; n++)
	{
		vector<int> temp;
		temp.push_back(n);
		dfs(n, temp);
	}
	
	cout << ans;
	return 0;
}

 

240412 재도전 

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

int N, K;
int ret = 0;
int minDiff = 1000000000;

void dfs(int s, int b, vector<pair<int, int>> v, int idx)
{
	//cout << "idx : " << idx << " s : " << s << ", b : " << b << endl;

	(s == 0) ? s += v[idx].first : s *= v[idx].first;
	b += v[idx].second;

	if (s != 0 && abs(s - b) < minDiff) {
		minDiff = abs(s - b);
	}

	for (int i = 1; i < v.size() - idx; i++)
		dfs(s, b, v, idx + i);
}

int main()
{
	cin >> N;
	vector<pair<int, int>> taste(N, make_pair(0, 0));
	int S = 0, B = 0;

	for (int i = 0; i < N; i++)
	{
		cin >> taste[i].first >> taste[i].second;
	}

	for(int i=0; i<N; i++) dfs(S, B, taste, i);
	cout << minDiff << endl;
	return 0;
}

---

#include<stdio.h>
#define diff(a,b) (a > b ? a - b : b - a)
int t[11][2];
int ans = 1000000001,n;
void search(int x, int a, int b)
{
	if (b > 0 && diff(a, b) < ans) ans = diff(a, b);
	if (x == n + 1)
		return;
	search(x + 1, a, b);
	search(x + 1, a*t[x][0], b+ t[x][1]);
}
int main()
{
	int i;
	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d %d", &t[i][0], &t[i][1]);
	search(0, 1, 0);
	printf("%d\n", ans);
}