[백준] 28447번 : 마라탕 재료 고르기 (C++)

28447번 : 마라탕 재료 고르기

---

문제)

하얔이는 마라탕에 여러 재료를 넣어 먹는 것을 좋아한다. 하지만 마라탕에 항상 많은 재료를 넣는다고 맛있는 것은 아니다. 마라탕은 각 재료마다 궁합이 존재해서 같이 넣으면 맛있는 재료도 있고 그렇지 않은 경우도 있다. 여기서 하얔이는 고민에 빠졌다.

 

대체 어떻게 해야 K개의 재료를 넣었을 때 마라탕의 맛을 최대로 할 수 있는거지?

 

 C_i, j를 재료 i와 재료 j를 같이 넣었을 때의 궁합이라 하자. 마라탕의 맛은 마라탕에 들어간 모든 재료 쌍의 궁합의 합이다.

고른 재료의 그룹을 G라고 했을 때 마라탕의 맛을 수식으로 표현하면 다음과 같다.

 

 

가여운 하얔이를 위해 재료를 K개만 사용했을 때의 최대의 마라탕의 맛을 구해보자.

 

 

 

입력 :

 

 

 

출력 :

첫째 줄에 K개의 재료만 사용한 마라탕의 맛의 최댓값을 출력한다.

 

 

 

 

 

 

풀이)

 

// 28447. 마라탕 재료 고르기
#include <iostream>
#include <vector>
#include <limits.h>
 
using namespace std;
 
int n, k;
vector<vector<int>> vec;
vector<int> choice;
 
int ans = INT_MIN;
 
void recur(int cur, int cnt)
{
    if (cnt > k) return;
    // 모든 조건을 살펴보았을 때.
    if (cur == n)
    {
        // 마라탕 재료는 무조건 k를 골라야 한다.
        if (cnt == k)
        {
            int res = 0;
            for (int i = 0; i < cnt; i++)
            {
                int x = choice[i];
                for (int j = i + 1; j < cnt; j++)
                {
                    int y = choice[j];
                    res += vec[x][y];
                }
            }
 
            // 정답 갱신
            ans = max(ans, res);
        }
        return;
    }
 
    choice[cnt] = cur;
    recur(cur + 1, cnt + 1);
    recur(cur + 1, cnt);
}
 
int main()
{
    cin >> n >> k;
    vec.resize(n, vector<int>(n));
    choice.resize(k + 1);
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> vec[i][j];
        }
    }
 
    recur(0, 0);
 
    cout << ans;
 
    return 0;
}
 
 

---

출처 : https://www.acmicpc.net/problem/28447 

28447번: 마라탕 재료 고르기