[백준 2961번 C/C++] 도영이가 만든 맛있는 음식

 

[백준 2961번 C/C++] 도영이가 만든 맛있는 음식

 

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

---

 

 

해결전략

 

비트마스킹 Bitmasking

 

---

 

처음 시도한 코드 - 시간초과

 

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int n;
long long answer = 987654321;
vector<int> sour, bitter;
vector<pair<int, int>> taste;

void DFS(int idx, vector<int>& ch, set<int>& foods)
{
	if (idx == n){
		long long sour = 1, bitter = 0;

		for (auto& iter : foods){
			sour *= taste[iter].first;
			bitter += taste[iter].second;
		}
        
		answer = min(answer, abs(sour - bitter));
		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (ch[i] == 0)
		{
			ch[i] = 1;
			foods.insert(i);
			DFS(idx + 1, ch, foods);
			foods.erase(i);
			ch[i] = 0;
		}
	}
}

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

	cin >> n;
	taste.resize(n);
	for (int i = 0; i < n; i++){
		cin >> taste[i].first >> taste[i].second;
	}

	for (int i = 0; i < n; i++)
	{
		vector<int> ch(n, 0);
		set<int> foods;

		DFS(i, ch, foods);
	}

	cout << answer << "\n";

	return 0;
}

---

 

 

정답코드

 

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

int n; // 재료의 개수
long long answer = 987654321; // 최종 답, 충분히 큰 값으로 초기화
vector<pair<int, int>> taste; // 재료의 신맛과 쓴맛을 저장

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

    cin >> n;
    taste.resize(n);
    for (int i = 0; i < n; i++){
        cin >> taste[i].first >> taste[i].second;
    }

	// 모든 경우의 수((1 << taste.size) -1). ex. n=3라면: 001, 010, 011, 100, 101, 111 
    // 비트마스크를 이용하여 모든 부분 집합을 탐색
    for (int bitmask = 1; bitmask < (1 << taste.size()); bitmask++)
    {
        long long sour = 1, bitter = 0; // 각 부분 집합의 신맛과 쓴맛을 계산할 변수 초기화

        // 비트마스크를 이용하여 현재 부분 집합에 포함된 재료를 탐색
        for (int i = 0; i < taste.size(); i++)
        {
            if (bitmask & (1 << i)){ // 현재 i번째 재료가 부분 집합에 포함되어 있는지 확인
                sour *= taste[i].first; 
                bitter += taste[i].second; 
                //cout << "-- " << taste[i].first << ", " << taste[i].second << "\n";
            }
        }

        //cout << sour << ", " << bitter << "\n\n";
        answer = min(answer, abs(sour - bitter));
    }

    cout << answer << "\n";

    return 0;
}

 

---