백준 2961번 도영이가 만든 맛있는 음식 C++

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

 

n개의 재료가 있는데, 각 재료에는 신맛과 쓴맛이 수치로 존재한다. 1개 이상의 재료를 사용해서 음식을 만드는데, 신맛과 쓴맛의 차이의 최솟값을 구하는 문제이다. 신맛은 재료들의 각각의 신맛의 수치를 곱한 값이 되고, 단맛은 재료들의 단맛을 더한 값이 된다.

 

처음에 문제를 분석할 때 신맛이 나는 재료와 단맛이 나는 재료가 분리되어 있다고 착각해서 조금 헤맸다.

문제를 다시 읽어보니 하나의 재료에 단맛과 신맛이 같이 있다는 것을 깨달았다.

그러고 나니 문제를 해결하는 방법이 쉽게 떠올랐다.

 

각각의 재료들의 신맛, 단맛 정보를 pair로 저장해서 벡터에 하나씩 삽입하고 벡터를 재귀적으로 돌면서 신맛과 단맛의 최솟값을 탐색하였다.

신맛이든 단맛이든 1, 2, 3이나 2, 3, 1이나 같은 값이 나오기 때문에 인덱스를 점점 늘려가면서 재귀함수를 통해 답을 구했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n;
vector<pair<int, int>> taste;
int ans = 1000000000;

void solve(int index, int mul, int sum) {
	if (index >= 1) {
		ans = min(ans, abs(mul - sum));
	}
	for (int i = index; i < taste.size(); i++) {
		solve(i + 1, mul * taste[i].first, sum + taste[i].second);
	}
}

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

	int a, b;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		taste.push_back({ a,b });
	}
	solve(0, 1, 0);
	cout << ans;
};