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

재료를 넣을지 말지 정해서

총합을 구하는 브루트포스 문제

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

1. 문제

---

간단 설명

각 재료는 신맛과 쓴맛의 점수를 가지고있음

재료를 넣어서 신맛과 쓴맛의 점수가 최소가 되는 값을 구하는 문제

2. 문제 분석

---

필요변수

재료 개수 N(1 ≤ N ≤ 10)

재료 구조체 ingredient. pair를 써도 상관없지만 가독성을 위해서 구조체 사용

신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수. int로 처리 가능

재료 정보를 저장할 vector<ingredient> gd

주의점

• 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

  최소 하나의 재료를 사용해야함

• 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다

  이 부분이 조금 애매하다고 생각함

  모든 재료를 사용하지 않았을 때는 그럼 10억보다 클수도 있다는건가?

  그럼 long long int 형을 써야하는건가 싶음

  신맛은 누적곱으로 증가하는데 그럼 10억^10이 될수도 있는데 오버플로우가 아닌가 싶다

• 일단은 long long int 형으로 처리함

  알고리즘

각 재료를 넣거나 안넣거나 하는 방식으로 재귀를 호출함

재귀를 호출하면서 신맛 점수와 쓴맛 점수를 각각 계산하여,

모든 재료의 사용 여부가 결정되었다면 점수들의 차이를 계산하여 최소값을 갱신한다

재료를 사용하면 사용여부를 used 벡터에 저장하여

재료를 하나도 안 쓴 경우를 제외할 수 있도록 한다

3. 소스코드

---

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

struct ingredient {
	int sour;
	int bitter;
};

int N;  
int result = 21e8;
bool ingredient_flag = false;
vector<ingredient> gd;
vector<int> used;

void run(int level, long long int sourPoint, long long int bitterPoint){
	// 모든 재료를 다 사용한 경우
	if (!used.empty() && level == N) {
		cout << abs(sourPoint - bitterPoint) << endl;
		if (abs(sourPoint - bitterPoint) < result) {
			result = abs(sourPoint - bitterPoint);
		}
		return;
	}
	if (level >= N) return;

	used.push_back(level); // 현재 재료를 썼다고 표시
	run(level + 1, sourPoint * gd[level].sour, bitterPoint + gd[level].bitter); // 사용하거나
	used.pop_back();

	run(level + 1, sourPoint, bitterPoint); // 안하거나
	return;
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	gd.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> gd[i].sour >> gd[i].bitter;
	}

	run(0, 1, 0);

	cout << result;

	return 0;
}