백준[baekjoon] 2961

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

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

[문제설명]

- n개의 재료를 각각 사용 또는 사용안해도 된다.

- 각 재료는 신맛 S와 쓴맛 B를 가지고 있다.

- 재료 선택을 마친 후 선택된 재료의 신맛을 곱하고 쓴맛은 더했을 때 두 값의 가장 작은 차이를 출력해야 한다.

- 재료는 적어도 하나 사용해야 한다.

 

[문제풀이]

- n개의 재료를 사용하거나 사용안해도 무방하니 재료선택의 총 경우의 수는 2^n입니다.

- n이 4일때 각 재료를 사용하거나 사용하지 않을때를 이진수로 표현하면 아래 그림과 같습니다.

- 문제를 Bottom-Up 방식으로 접근하자면 [0...2^n]을 작은 값(재료 선택의 결과)부터 채워나가는 방식이며 6일경우를 그림과 함께 설명해보겠습니다.

재료 선택의 결과 값이 6일때의 의미는 그림과 같이 0, 3번째 재료는 사용하지 않았으며 1, 2번째 재료는 사용되었음을 의미합니다.

 

- x번째 재료가 사용되었으면 1*(2^x)값이 사용되지 않았을 경우에는 0*(2^x)값이 재료 선택 값에 더해집니다.

 

- Bottom-Up 방식으로 접근할 경우 재료 선택 값 6일때의 해석은 아래 그림과 같습니다.

재료 선택 값을 작은값부터 순차적으로 채워 나가기 때문에 재료 선택 값이 6일때의 결과를 얻을시점에는 [0...6)에 대한 결과를 알 수 있습니다. 따라서 msb번째 재료를 분리시켜 점화식을 완성시킬 수 있습니다.

 

- (msb재료 + 이전상태) -> (현재상태)를 시각화 해보면 아래 그림과 같습니다.

- 문제에서는 최소 한개 이상의 재료가 사용됨을 보장하였지만 아무 재료를 선택하지 않은 경우(0) 을 basis로 잡아 최소 한개 재료부터 모든재료까지 선택한 경우에 대한 (신맛, 쓴맛)의 곱과 합을 채운 후 두 값의 차이 최소값을 알아내면 됩니다.

 

[코드]

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 10;
const int INF = 0x3f3f3f3f;

pii food[MAX_N];   // {S, B}
pii ret[1 << MAX_N];
int n;

int msb(int b) {
	for(int i=n-1; i>=0; --i) {
		if(b & (1 << i)) return i;
	}

	return -1; // fail
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> food[i].first >> food[i].second;
	}

	int ans = INF;
	ret[0] = {1, 0}; // basis
	for(int i=1; i<(1<<n); ++i) {
		int cur = msb(i);
		ret[i].first = ret[i ^ (1 << cur)].first * food[cur].first;
		ret[i].second = ret[i ^ (1 << cur)].second + food[cur].second;
	
		ans = min(ans, abs(ret[i].first - ret[i].second));
	}

	cout << ans << '\n';
	return 0;
}