백준 BOJ 2961 - 도영이가 만든 맛있는 음식

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

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

신맛과 쓴맛이 최대한 비슷해지게 만드는 문제.

N이 10으로 매우 작아서

O(2^N) 시간복잡도를 가지는 브루트포스로도 문제를 해결할 수 있다.

해당 문제의 구현 방법으로는 재귀함수를 사용한 구현과(dfs-like)

비트마스킹을 이용한 구현이 있는데, 비트마스킹을 연습하기에 나쁘지 않은 유형이지 싶어서

비트마스킹으로 풀어보았다.

 

i번 재료를 섞는 경우에 i번 비트를 1로 켜고,

i번 재료를 섞지 않는 경우에 i번 비트를 0으로 끄면

모든 재료를 섞거나 섞지 않는 경우의 수는

 

0 비트 N개 ~ 1 비트 N개 까지로,

이를 구간으로 표현하면

[0, (1<<N)-1] 이다.

여기서, 아무런 재료도 선택하지 않는 경우는 없으므로

탐색하고자 하는 구간을

[0, (1<<N)-1] 이 아닌

[1, (1<<N)-1] 으로 설정해야 함에 주의

 

#include<bits/stdc++.h>
using namespace std;

vector<int> S;
vector<int> B;

int main(){
	int N,a,b;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> a >> b;
		S.push_back(a);
		B.push_back(b);
	}
	
	int ans = 998244353;
	
	for(int i=1; i<(1<<N); i++){
		int tmp = i;
		int s=1;
		int b=0;
		for(int j=0; tmp; j++){
			if(tmp%2 == 1){
				s *= S[j];
				b += B[j];
			}
			tmp /= 2;
		}
		
		ans = min(ans, abs(s-b));
	}
	cout << ans;
	return 0;
}