BOJ 28447 : 마라탕 재료 고르기

• 문제 링크 : boj.kr/28447
• 난이도 : S2
• 태그 : 브루트포스

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n, k;
    cin >> n >> k;

    vector<vector<int>> arr(n, vector<int>(n));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }

    int ans = -INF;
    for(int s = 0; s < (1 << n); s++) {
        bitset<10> bs(s);
        if(bs.count() != k) continue;

        int sum = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(bs[i] & bs[j]) sum += arr[i][j];
            }
        }
        ans = max(ans, sum/2);
    }
    cout << ans;

    return 0;
}

---

풀이

백트래킹으로 풀 수도 있지만, n이 크지 않기 때문에 가능한 모든 조합으로 골라보고 그 중 고른 재료의 갯수가 K개인 경우에 대해서 확인할 수도 있다.