취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2961번 문제인 도영이가 만든 맛있는 음식이다.
문제는 아래 링크를 확인하자.

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

모든 재료를 이용하지 않은 한 가지 경우를 제외한 2^N-1가지 요리의 신맛과 쓴맛의 정도를 직접 계산해 문제를 해결하자.

요리의 종류는 많아야 2^10-1 = 1023가지뿐이므로 충분히 빠르게 모든 경우의 수를 살펴볼 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int ans = 1000000000;
int sour[10], bitter[10];

void func(int idx, int s, int b) {
	if (idx == N) {
		if (b) ans = min(ans, abs(s - b));
		return;
	}
	func(idx + 1, s, b);
	func(idx + 1, s * sour[idx], b + bitter[idx]);
}

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> sour[i] >> bitter[i];

	func(0, 1, 0);

	cout << ans;
}