🖊️ 문제

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

---

🖊️ 풀이

각 재료들에 대해, 공집합을 제외한 모든 부분집합을 구해야 하는게 키포인트인 문제였다.

사실,.. 이거 전에 풀었는데
내가 기억을 하나도 못하고 있었다.

진짜 하... 레전드

그냥 다시 공부한다치고 여기다 다시 적는다.

주어진 테스트케이스에 대해서 생각해보면
먼저 재료가 4개 있다.

재료 4개에 대한 공집합을 제외한 부분집합은
0001
0010
0100 (2번째 재료만 선택)
1000
0011
0110
1100 (1, 2번째 재료만 선택)
1010
1001
0101
1110
1101
1001
0111
1111

이렇게 총 15개.

이 부분집합들을 구할거다.

일단,, n이 주어진 상황에서 n에 대한 부분집합의 경우의 수를 구하려면, 1부터 10000 직전까지 돌면 되겠따. 10000 -> (1 << n)

그래서 이만큼에 대해 비교해준다.

근데 이제,
예를 들어서 1100일 때 어떤 재료를 선택했는지를 판별하기 위해서는,
각 재료 인덱스를 의미하는 것들과 연산한다.

1000, 0100, 0010, 0001과 각자 &연산을 해주면, 1000과 0100은 1이, 0010과 0001은 0이 나온다.

1이 나온 1000과 0100은? 이 재료가 선택됐다는 뜻.

여기서 1000, 0100, 0010, 0001은?
1을 3번 밀고, 2번 밀고, 1번 밀고, 0번 민 것.
그래서 이걸 코드로 해보면

for (int i = 0 ; i < (i << n) ; i++) {
	for (int j =0 ; j < n ; j++) {
		if (i & (1 << j)) {
        	// 재료 선택됨
        }
    }
}

비로소 몬가 .. 이해됐다.

휴
진짜
난
바보가 틀림없다.

이렇게 각 부분집합만 구해주면 나머지는 넘 쉬운ㅇ 문제!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

바부

그래도 !! 이제 까묵지말자

따봉 도영아 고마워!!! ❤️❤️❤️❤️

#include <iostream>
#include <limits.h>
using namespace std;

typedef long long ll;
ll arr[10][2];

int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}

	ll result = LLONG_MAX;
	for (int i = 1; i < (1 << n); i++) {
		ll s = 1;
		ll b = 0;
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {
				s *= arr[j][0];
				b += arr[j][1];
			}
		}
		result = min(result, abs(s - b));
	}
	cout << result << endl;
}