[백준] 발전소(1102)

문제 링크 : [백준] 발전소(1102)

문제 설명

발전소의 갯수와 발전소끼리 재시작하는 비용이 인접행렬로 주어지고,
각 발전소가 정상동작중인지 상태가 주어집니다.
마지막으로 최소한 동작해야하는 발전소의 갯수가 주어진다면,
인접행렬의 비용들을 이용하여 최소한 동작해야하는 발전소 갯수 이상의 발전소를 동작시키기 위한 최소 비용을 구하세요.
최소 비용을 구할 수 없으면 -1을 출력합니다.

입력

N(발전소의 수, 1 <= N <= 16)
V_ij(i번째 발전소가 j번째 발전소를 재시작하는데 필요한 비용, 0 <= V_ij <= 50)
S(발전소의 상태, Y는 가동중, N은 고장)
P(최소한 동작해야하는 발전소의 수, 0 <= P <= N)

3
0 10 11
10 0 12
12 13 0
YNN
3

출력

21

카테고리

#DP #비트마스크

시간 복잡도 상한

O(N!)만 아니면 될 것 같습니다.

해결 방법

1. -1을 출력하는 경우에 대해서 먼저 생각해봅니다.
   1-1. 모든 발전소가 고장난 상태에서 1개 이상의 발전소를 켜야하는 경우는 불가능한 경우입니다.
2. N이 작고, 각각의 상태가 0과 1로 나타낼 수 있으며, 그 상태들의 변화에 대한 내용들이므로 비트마스크를 고민해볼 수 있습니다.
3. 각 발전소의 상태를 한개의 비트로 표시할 수 있으며, 16bit, 즉 64000개 내의 상태로 표시할 수 있습니다.
4. 처음 주어진 상태에서 하나씩 발전소를 켜는 행위를 재귀로 반복하여 합니다.(모든 출발점에서 모든 도착점까지)
   4-1. 반복하면서, 기존에 켜져있던 발전소이면 continue
   4-2. 출발 발전소가 꺼져있는 상태라면 continue
   4-3. 다음 발전소 하나를 켰을 때 중 최소 값을 구합니다.
5. 4의 조건들을 가지고 재귀를 반복하며 켜진 발전소가 P개가 될때까지 반복합니다.

시간복잡도

O(2ⁿ * n * n)

코드

#include<cstdio>
#include<algorithm>
int n,m,k,d[16][16],e[1024*64],v[1024*64],i,j;
char s[17];
int r(int s){
    int x=0;
    for(int i=0;i<n;i++)x+=!!(s&(1<<i));
    if(x>=m)return 0;
    if(v[s])return e[s];
    v[s]=1;
    e[s]=99999;
    for(int i=0;i<n;i++){
        if(!(s&(1<<i))){
            for(int j=0;j<n;j++){
                if(i==j)continue;
                if(s&1<<j)e[s]=std::min(e[s],d[j][i]+r(s|1<<i));
            }
        }
    }
    return e[s];
}
int main(){
    scanf("%d",&n);
    for(i=0;i<n;i++)for(j=0;j<n;j++)scanf("%d",d[i]+j);
    scanf("%s%d",s,&m);
    for(i=0;s[i];i++)k|=((s[i]=='Y')<<i);
    if(!m)printf("0");
    else printf("%d",k==0||n<m?-1:r(k));
}