[BOJ] 2961. 도영이가 만든 맛있는 음식 (bitmask, bruteforcing)

Silver II

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

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

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

 

input:

• 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다.
• 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다.
• 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

output:

• 첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다.

 

---

Idea 1: using DFS

• 가능한 모든 재료 조합에 대해 쓴맛, 신맛을 계산 → 조합 문제 ⇒ DFS

Code 1-1:   

#include <iostream>

using namespace std;

int N;
unsigned int sour[11] = {};
unsigned int bitter[11] = {};
unsigned long long min_diff = 10000000000;

/* dfs: dfs를 이용하여 사용할 재료 조합을 구하고, 쓴맛 신맛 차이를 계산
 *
 * parameters - depth: dfs의 깊이, 사용한 재료의 개수
 *            - mul, sum: 사용한 재료로 계산한 쓴맛, 신밋
 *            - visited: 사용한 재료 체크
 * return - none
 */
void dfs(int depth, long long mul, long long sum, int visited) {
	// 쓴맛 신맛 차이 & 답 구하기
	unsigned long long diff = abs(mul - sum);
	if (diff < min_diff) 
		min_diff = diff;

	// 재귀 종료 조건
	if (depth == N)
		return;

	// dfs, 재귀를 이용해 조합 구하기
	for (int i=0; i<N; i++) {
		if ((visited & (1 << i)) != 0) continue;
		dfs(depth + 1, mul * sour[i], sum + bitter[i], visited | (1 << i));
	}
}

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

	// freopen("input.txt", "rt", stdin);

	/* input */
	cin >> N;
	for (int i=0; i<N; i++)
		cin >> sour[i] >> bitter[i];

	/* solve */
	for (int i=0; i<N; i++)
		dfs(1, sour[i], bitter[i], (1 << i));

	/* print answer */
	cout << min_diff << "\n";
}

 

Code 1-2:

• 트리의 depth를 재료의 인덱스로 하고, 각각의 재료에 대해 넣거나 넣지 않거나 2가지 경우를 고려
• N개 중 특정 m개의 원소를 골라 조합/순열을 만드는 문제가 아니므로 depth를 depth 번째에 들어갈 원소가 아니라 depth 번째 원소로 하는 것이 더 효율적

#include <iostream>

using namespace std;

int N;
int sour[10] = {};
int bitter[10] = {};
unsigned int min_diff = 1000000000;

unsigned int get_minDiff(long long mul, long long sum) {
	unsigned int diff = abs(mul - sum);
	if (diff < min_diff) return diff;
	else return min_diff;
}

void dfs(int depth, long long mul, long long sum) {
	if (depth == N) return;
	min_diff = get_minDiff(mul * sour[depth], sum + bitter[depth]);

	dfs(depth + 1, mul * sour[depth], sum + bitter[depth]); // depth 번쩨 재료를 포함하는 경우
	dfs(depth + 1, mul, sum);                               // depth 번쩨 재료를 포함하지 않는 경우
}

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

	// freopen("input.txt", "rt", stdin);

	cin >> N;
	for (int i=0; i<N; i++)
		cin >> sour[i] >> bitter[i];

	dfs(0, 1, 0);

	cout << min_diff << "\n";
}

---

Idea 2: using Bitmasking

• DFS로 문제를 해결할 경우 시간 내에 해결은 가능하나 비효율적
• N개 중 특정 개수로 구성된 조합을 만드는 것이 아니라 N개로 만들 수 있는 모든 부분집합에 대해 쓴맛 신맛을 계산해야됨
• 비트마스킹을 이용해 부분집합을 구하는 것이 시간, 메모리 측면에서 훨씬 효율적

 

• 비트마스킹을 이용한 부분집합 구하기
  • 부분집합의 개수 = 2^N - 1 = (1 << N) - 1
  • 0부터 (1 << N) - 1 까지로 부분집합을 표현할 수 있음

ex) N = 3, {a, b, c}

부분집합	{}	{a}	{b}	{c}	{a, b}	{a, c}	{b, c}	{a, b, c}
비트마스크	000	001	010	100	011	101	110	111
10진수	0	1	2	4	3	5	6	7

 

Code 2: 

#include <iostream>

using namespace std;

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

	// freopen("input.txt", "rt", stdin);

	int N;
	int sour[10] = {};
	int bitter[10] = {};
	unsigned int min_diff = 1000000000;

	/* input */
	cin >> N;
	for (int i=0; i<N; i++)
		cin >> sour[i] >> bitter[i];

	/* solve */
	// 비트마스킹을 이용한 부분집합 구하기
	for (int set=1; set < (1<<N); set++) {
		int mul = 1, sum = 0;
		// 부분집합에 속한 재료로 쓴맛, 신맛 값 계산
		for (int i=0; i<N; i++) {
			if ((set & (1 << i)) != 0) {
				mul *= sour[i]; sum += bitter[i];
			}
		}
		// 쓴맛 신맛 차이 계산 및 답 구하기
		unsigned int diff = abs(mul - sum);
		if (diff < min_diff) 
			min_diff = diff;
	}
	
	/* print answer */
	cout << min_diff << "\n";
}

 

---

Result : 

code 1-1) 메모리: 2020 KB,  시간: 136 ms

code 1-2) 메모리: 2020 KB,  시간: 0 ms

code 2) 메모리: 2020 KB,  시간: 0 ms

 

Review :

• 부분집합 문제와 조합 / 순열 문제 구분하자
• 부분집합은 비트마스킹, 조합/순열은 dfs
• 부분집합에 dfs를 이용할 수도 있음 + 비트마스킹보다 더 효율적일 수 있음