[BOJ] 2961번 도영이가 만든 맛있는 음식 (C++)

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

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

 

#include <iostream>
#include <cmath>
using namespace std;

int n;
int ans = 987654321;
int ingredients[10][2];

int main() {
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> ingredients[i][0];
		cin >> ingredients[i][1];
	}
	int noc = 1 << n;  // 모든 경우의 수
	for(int i = 1; i < noc; i++){  // 공집합(0) 제외
		int sour = 1;
		int bitter = 0;
		for(int j = 0; j < n; j++){
			if((i & (1 << j)) != 0){  // 해당 재료가 경우의 수에 포함되어 있는지
				sour *= ingredients[j][0];
				bitter += ingredients[j][1]; 
			}
		}
		if(abs(sour - bitter) < ans){
			ans = abs(sour - bitter);
		}
	}
	cout << ans;
	return 0;
}

 

백트래킹으로 풀 수도 있는 문제이지만, 비트마스킹을 활용하여 부분집합을 구해보았다.

 

 

먼저 재료를 선택하는 모든 경우의 수 noc를 구한다. 모든 경우의 수는 2^n 개이다.

예를 들어, 재료의 개수가 3개(a, b, c)라면 가능한 경우의 수는 선택X, a, b, c, ab, ac, bc, abc으로 총 8(2^3)개이다. 

이 때, 재료를 하나도 선택하지 않는 경우는 없으므로 공집합(0)은 제외한다.

 

1부터 noc - 1까지 경우의 수(001, 010, 011, 100, 101, 110, 111)와 각각의 재료(001, 010, 100)을 &(AND) 연산하면 재료가 경우의 수에 포함되어 있는지 알 수 있고 (비트연산 게시물 참고!!) 재료가 포함되어있는 경우에 연산을 해 준다.

 

경우의 수마다 신맛과 쓴맛의 차이를 계산하여 가장 작은 신맛과 쓴맛의 차이를 구한다.