발전소 - 1102

//1102 - 발전소
 
#include <iostream>
#include <vector>
using namespace std;
 
#define INF 2000000000
 
int N;
int arr[16][16];
int fstate = 0;
int cond;
vector<int> cache;
 
void init()
{
    cin >> N;
    for(int i = 0; i<N; ++i)
        for(int j = 0; j<N; ++j)
            cin >> arr[i][j];
    string s;
    cin >> s;
    for(int i = 0; i<s.size(); ++i)
        if(s[i] == 'Y')
            fstate |= (1 << i);
    cin >> cond;
    cache = vector<int>(1<<N, -1);      
}
 
int dp(int state)
{
    if(__builtin_popcount(state) >= cond)
        return 0;
    int& ret = cache[state];
    if(ret != -1)
        return ret;
    ret = INF;
    for(int i = 0; i<N; ++i)
        if(!(state & (1<<i)))
            for(int j = 0; j<N; ++j)
                if((state & (1<<j)))
                    ret = min(ret, dp(state | (1<<i)) + arr[j][i]);
    return ret;
}
 
int main()
{
    init();
    int ans = dp(fstate);
    if(ans == INF)
        cout << -1;
    else
        cout << ans;
}

 

 

 

 

 

 

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

1102번: 발전소

 

 

 

 

 

 

발전소

DP와 비트마스크를 이용했습니다!