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

0. 문제 설명

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

입력	출력
1 3 10	7
2 3 8 5 8	1
4 1 7 2 6 3 8 4 9	1

1. 접근

• 단순히 재료를 넣는지 마는지에 따라 결과의 최솟값을 구하는 문제
• 반복적이므로 재귀를 통해 해결했다
  -> 하지만 이 문제는 밑의 비트마스킹 방법을 사용하는것이 더 효율적인 것 같다

2. 나의 풀이

/*
221118
백준 2961 : 맛있는 음식
https://www.acmicpc.net/problem/2961
*/

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


/**
* @brief index 번째의 재료를 넣거나 넣지 않았을 때의 맛의 차이를 구하는 함수
*
* @param {vector<pair<int, int>>} Ingredients : 각 재료들의 <쓴맛, 신맛> 데이터
* @param {int} index : 현재 넣을지말지 결정할 인덱스 값
* @param {int} nowS : 현재까지의 쓴맛
* @param {int} nowC : 현재까지의 신맛
* @param {int*} ret : 결과값을 담을 ret 포인터
**/
void FindMinSub(vector<pair<int, int>> Ingredients,int index, int nowS,int nowC, int* ret) {
	if (index == Ingredients.size()) {
		return;
	}

	FindMinSub(Ingredients, index + 1, nowS, nowC, ret); //재료를 넣지 않는 경우

	nowS *= Ingredients[index].first; //재료를 넣는 경우, 그 재료를 포함하여 합연산, 곱연산을 한다
	nowC += Ingredients[index].second;
	*ret = min(*ret, abs(nowS - nowC));

	FindMinSub(Ingredients, index + 1, nowS, nowC, ret);
	return;
}

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

	int n;
	cin >> n;
	int ret = -1;

	vector<pair<int, int>> Ingredients(n); //재료들의 <신맛 , 쓴맛>
	for (int i = 0; i < n; i++) {
		int s, c;
		cin >> s >> c;
		Ingredients[i] = make_pair(s, c);

		//값을 넣으면서 재료가 1개씩 들어간 경우 중 최솟값으로 ret의 초기값을 설정한다
		if (ret == -1) ret = abs(s - c);
		else ret = min(ret, abs(s - c));
	}

	FindMinSub(Ingredients, 0, 1, 0, &ret);
	cout << ret << "\n";
	return 0;
}

3. 다른 사람의 풀이

비트마스킹

https://ezeun.tistory.com/205

이 문제에만 해당할 수 있어 범용적이진 않더라도 좋은 방식인 것 같다
결국 재료 1개를 쓰는지마는지는 0,1값으로만 판단하게 되므로

0001 : 4번째 재료만 사용
1100 : 1,2 번째 재료만 사용

으로 이해할 수 있게 된다

• 조건문의 i<(1<<n) 은 i<2^(n-1) 로 이해할 수 있다.
• 재료가 5개라면 11111 까지 되어야 하는데, 1(000001) 을 5번 << 하면, (100000)이 되므로, 11111보다는 크고, 111111(재료 6개) 인 경우보다는 작아진다!

#include <iostream>
#include <vector>

using namespace std;

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

    int ans=2147483647;
    vector<pair<int,int>> v;

    int n; cin>>n;
    for(int i=0; i<n; i++){
        int a,b; cin>>a>>b;
        v.push_back({a,b});
    }


    for(int i=1; i<(1<<n); i++){ // 1(00..001) 부터 2^n-1(11..111)까지 (n자리수)
        int a=1, b=0;
        for(int x=0; x<n; x++){ // 최대 n-1칸 shiftleft
            if(i & (1<<x)){ //조건문 결과가 1이면 해당 재료 사용한거임 
                a*= v[x].first;
                b+= v[x].second;
            }
        }
        ans=min(ans, abs(a-b));
    }
    cout<<ans;
    return 0;
}

조합

https://ongveloper.tistory.com/305
조합으로 넣을 재료의 인덱스를 먼저 구하고, 그 때의 값을 갱신한다
'조합' 이라는 키워드의 차이가 있어 가져왔지만 내 코드도 결국 조합과 원리는 같기 때문에 코드 틀은 비슷하다