백준 2961 도영이가 만든 맛있는 음식 c++ (완전탐색)

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

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

문제

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

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

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

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

입력

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

출력

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

2, 3, 4번 재료를 사용한다면, 요리의 신맛은 2×3×4=24, 쓴맛은 6+8+9=23이 된다. 차이는 1이다.

알고리즘 분류

• 브루트포스 알고리즘
• 비트마스킹

풀이

완전 탐색을 기반으로 한 조합 문제이다.

기본 조합 문제와 다른 점은, 배열의 값이 하나가 아닌 쌍으로(pair) 두 개의 값이 저장되는 것이고,

구한 재료들의 조합을 이용해 쓴맛과 신맛의 합을 구한 후 차이의 최솟값을 갱신하면 된다.

즉, 4개의 조합이 있다면, 1,2,3,4 재료들 중, {1}, {2}, {3}, {4}, {1,2}, {1,2,3}, {1,2,3,4}, {2, 3, 4}등의 모든 조합의 신맛과 쓴맛의 차이를 구하면 된다. 

 

코드

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

int n;
pair<int, int> input[10];
//1<=n<=10
pair<int, int> result[10];
int answer = 987654321;
void combination(int idx, int cnt) {
	if (cnt > 0) {
		int s = result[0].first;
		int b = result[0].second;
		for (int i = 1; i < cnt; i++) {
			s *= result[i].first;
			b += result[i].second;
		}
		answer = min(answer, abs(s - b));
	}
	if (cnt == n) {
		return;
	}
	for (int i = idx; i < n; i++) {
		result[cnt] = { input[i].first,input[i].second};
		combination(i + 1, cnt + 1);
	}
}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input[i].first;
		cin >> input[i].second;
	}
	combination(0,0);
	cout << answer;
	return 0;
}