2. 2961 도영이가 만든 맛있는 음식

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

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

#include <iostream>
using namespace std;
typedef struct ingredient {
	int sourness;	// 신맛
	int bitter;		// 쓴맛
}Ingredient;

int tmpArr[100];
int sournessArr[100];
int bitterArr[100];
long long int min_num = 999999999999999;

void printCombination(Ingredient arr[], int index){
	int tmp = 0, sourness = 1, sweetness = 0;
	for (int i = 0; i < index; ++i){
		sourness *= sournessArr[i];
		sweetness += bitterArr[i];
	}
	tmp = sourness - sweetness;
	if (tmp<0){
		tmp *= -1;
	}
	if (min_num>tmp){
		min_num = tmp;	//가장 작은 값만 대입
	}
//	printf("%d\n", tmp);
}
void Comb(Ingredient arr[], int index, int n, int r, int target){	//target은 출력할 횟수
	if (r == 0){	//다 뽑은 경우
		printCombination(arr, index);
	}
	else if (target == n) return;	// r개를 다 뽑았는데 arr의 모든 원소를 다 검사할 때. 실패 : 아무것도 안함
	else{
		sournessArr[index] = arr[target].sourness;
		bitterArr[index] = arr[target].bitter;
		Comb(arr, index + 1, n, r - 1, target + 1);
		Comb(arr, index, n, r, target + 1);
	}
}//end combination()

int main(){
	//조합을 이용해서 경우의 수 다 뽑아 낸 후
	//최소값일 때 마다 넣어주기
	//nC1 nC2 nC3 nC4.. nCn-1 는 for문으로 구현해야 함.
	//조합 https://gorakgarak.tistory.com/523?category=265216
	//http://bitly.kr/kT2z3Y

	int num;
	scanf("%d", &num);
	Ingredient *ing = new Ingredient[num];
    //입력을 받은 뒤 조합으로 경우의 수 모두 출력 ... 모든 경우의 수 중 최소값만 저장
	for (int i = 0; i < num; i++){
		scanf("%d %d", &ing[i].sourness, &ing[i].bitter);
	}
	for (int i = 1; i <= num; i++){
		Comb(ing, 0, num, i, 0);
	}
	cout << min_num << endl;
	return 0;
}

1. 조합으로 모든 경우의 수를 계산

2. 모든 경우의 수 중 최소값만 저장