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

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

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

#include <cstdio>
#include <cstdlib>
int N;
int S[10 + 2];
int B[10 + 2];
int choice[10 + 2];
long long int min = 0x7fffffffffffffff;		// long long int 최대


void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &S[i], &B[i]);
	}
}

void Combi(int n, int s, int r)
{
	if (n == r) {
		long long int sour = 1; long long int bitter = 0;
		for (int i = 0; i < r; i++) {
			sour *= S[choice[i]];
			bitter += B[choice[i]];
		}
		long long int perkit = abs(sour - bitter);
		if (perkit < min) min = perkit;
	}

	for (int i = s; i < N; i++) {
		choice[n] = i;
		Combi(n + 1, i + 1, r);
	}
}



void get_num(void)
{
	for (int r = 1; r <= N; r++) {
		Combi(0, 0, r);
	}
}

int main()
{
	input();
	get_num();
	printf("%lld", min);
	return 0;
}

 

// input( ) 함수

신맛과 쓴맛을 S와 B배열에 따로따로 받아주었다. 

 

 

// get_num( ) 함수

N개 중 몇 개를 선택할 것인지 결정하는 함수이다. 

문제에서 "재료는 적어도 하나 사용해야 한다"라고 제시되어 있으므로 r = 1, 즉 N개 중 1개 선택하는 경우부터 r = N 즉, N개 중 N개 선택하는 경우까지 모두 탐색할 것이다. 

 

 

// Combi( ) 함수

재료를 1개 선택했을 때, 2개 선택했을 때, ..... N개 선택했을 때를 모두 살피면서 각 경우의 수에서의 신맛과 쓴맛을 계산한다. sour과 bitter는 신맛과 쓴맛 각각의 초기값인데, 신맛은 사용한 재료의 곱으로 나타낸다고 했으므로 그의 항등원인 1이고 쓴맛은 사용한 재료의 합으로 나타낸다고 했으므로 그의 항등원인 0으로 놓았다. 

그리고 신맛과 쓴맛의 차의 절댓값을 perkit 변수에 담아 min(우리가 구하려는 최솟값)과 비교하여 작으면 갱신한다.