[Silver II] 마라탕 재료 고르기

[문제 위치]

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

[문제 풀이]

이 문제는 N이 최대 10으로 작으므로 완전 탐색으로 해결할 수 있다.

먼저 N개의 재료 중 K개를 고르는 모든 경우를 만들어야 한다. 그 방법은 비트마스크를 쓰거나 조합을 생성하는 방법을 쓰면 된다. 각 경우마다 선택된 재료들의 모든 쌍을 확인해서 궁합 값을 합산한다.

합산한 값들 중 최댓값을 갱신해 나간다. 모든 경우를 다 확인한 뒤 최종적으로 얻은 최댓값을 출력하면 된다. 이렇게 하면 문제를 해결할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, K;
    if (!(cin >> N >> K)) return 0;
    vector<vector<int>> C(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> C[i][j];
    
    long long best = LLONG_MIN;
    // 비트마스크로 크기 K 부분집합을 모두 순회.
    for (int mask = 0; mask < (1 << N); ++mask) {
        if (__builtin_popcount((unsigned)mask) != K) continue;
        long long s = 0;
        for (int i = 0; i < N; ++i) if (mask & (1 << i))
            for (int j = i + 1; j < N; ++j) if (mask & (1 << j))
                s += C[i][j];
        best = max(best, s);
    }
    // K = 1이면 쌍이 없으니 합은 0이 최대가 됨.
    if (K == 1) best = 0;
    cout << best << '\n';
    return 0;
}