백준 2961 c++ : 완전탐색, 비트마스크

비트마스크?

N이 3이라면 bit 변수는 000, 001, 010, 011, 100, 101, 110, 111 로 표현될 수 있다.
그래서 각각 000 = 하나의 재료도 선택 안함, 001 = 3번 재료만 선택함 이런 식으로 비트 이동만으로 모든 조합을 구할 수 있다.

1 << i : i번째 비트만 1인 값
bit & (1 << i) : i번째 비트가 1인지 확인
(1 << N) : 2^N 수행

C++

int N = 3;  // 재료 개수
for (int bit = 1; bit < (1 << N); ++bit) {
    cout << "조합: ";
    for (int i = 0; i < N; ++i) {
        if (bit & (1 << i)) {
            cout << i << " ";  // i번 원소가 선택됨
        }
    }
    cout << "\n";
}

Java

int N = 3;
for (int bit = 1; bit < (1 << N); bit++) { // 공집합 제외
     System.out.print("조합: ");
     for (int i = 0; i < N; i++) {
         if ((bit & (1 << i)) != 0) {
            System.out.print(arr[i] + " ");
         }
     }
     System.out.println();
}

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void input_data(vector<pair<int, int>>& flavor) {
	int N, i, S, B;

	cin >> N;
	for (i = 0; i < N; i++) {
		cin >> S >> B;
		flavor.push_back({ S, B });
	}

	return;
}

int find_answer(vector<pair<int, int>>& flavor) {
	int answer = 1000000000;
	int S_sum, B_sum, N = flavor.size(), i;

	//비트마스크?
	for (int bit = 1; bit < (1 << N); bit++) {
		S_sum = 1;
		B_sum = 0;

		for (i = 0; i < N; ++i) {
			if (bit & (1 << i)) {
				S_sum *= flavor[i].first;
				B_sum += flavor[i].second;
			}
		}
		answer = min(answer, abs(S_sum - B_sum));
	}

	return answer;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<pair<int, int>> flavor;

	input_data(flavor);
	cout << find_answer(flavor) << "\n";

	return 0;
}