[1102] 발전소

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

1102번: 발전소

<문제>

외판원순회랑 비슷하게 완전탐색해주면 된다.

어떤 발전소를 켰는지를 비트마스킹으로 표현해주었다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int INF = 54321;
int n, p, ans = INF, a[17][17], dp[1 << 16];
int f(int cnt, int bt) {
    if (cnt >= p) return 0;
    if (dp[bt] != -1) return dp[bt];
    dp[bt] = INF;
    int i, j;
    for (i = 0; i < n; i++) {
        if (bt & (1 << i)) continue;
        for (j = 0; j < n; j++)
            if (bt & (1 << j))
                dp[bt] = min(f(cnt + 1, bt | (1 << i)) + a[j][i], dp[bt]);
    }
    return dp[bt];
}
int main(void) {
    memset(dp, -1, sizeof(dp));
    int i, j;
    cin >> n;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) cin >> a[i][j];
    string s;
    cin >> s;
    int bt = 0, S = s.length(), cnt = 0;
    for (i = 0; i < S; i++)
        if (s[i] == 'Y') {
            bt |= (1 << i);
            cnt++;
        }
    cin >> p;
    int ret = f(cnt, bt);
    if (ret == INF)
        cout << "-1";
    else
        cout << ret;
    return 0;
}