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

c++ 문제풀이

 

 

 

 

---

 

 

 

[백준 2961번 도영이가 만든 맛있는 음식 문제]

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

 

 

 

 

---

 

풀이 코드

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

int n;
int S[10], B[10];
long long Min = 1000000000;
void func(int cnt, int idx, long long s, long long b)
{
    if (cnt >= 1 && abs(s - b) < Min)
        Min = abs(s - b);
    if (idx == n) return;
    func(cnt + 1, idx + 1, s * S[idx], b + B[idx]);
    func(cnt, idx + 1, s, b);
}

int main(void)
{   
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> S[i] >> B[i];

    func(0, 0, 1, 0);
    cout << Min;

    return 0;
}

 

재료 하나에 대해서 사용했는지 안했는지를 이용하여 트리 형식으로 구현하였습니다. 신맛과 쓴맛을 배열에 저장하고 함수에 들어온 신맛과 쓴맛이 현재 최소값보다 작은지 판별합니다. 그 뒤에 다음 재료를 사용했을 경우로 func를 부른뒤 다음 재료를 사용하지 않았을 경우로 func를 불러줍니다. 이렇게 하면 모든 경우의 수 중에 가장 신맛과 쓴맛이 작은 경우의 수를 얻을 수 있습니다!

 

저는 트리 형식으로 문제를 풀었지만 다른 방식으로도 풀어도 괜찮습니다.