[백준 1102] 발전소

 

 

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

1102번: 발전소

 

비트 마스크를 이용하는 DP 문제.

 

처음에는 현재 방문 중인 발전소의 노드 번호가 필요한 줄 알고 삽질했다.

코드를 작성하다보니 현재 노드 번호에서부터 다음 발전소로 넘어가게 되면 또 무조건 출발지는 다음 발전소에서 그다음 발전소로 가는 오류가 있었다.

그래서 노드번호를 버리고 이중 for문을 돌리기로 하였다.

 

일단 완전탐색으로 풀었다. 예상한대로 시간 초과였다.

// 완전 탐색 --> 시간 초과
void fix(int price, int situation){
    if(price > miniPrice)
        return;
    
    if(__builtin_popcount(situation) == p){
        miniPrice = min(miniPrice, price);
        return;
    }
    // 무조건 cur에서 출발해야한다는 조건 없음
    for(int i = 0; i < n; i++){
        // i 번째 발전소 켜져있어야 다른 발전소를 작동 가능.
        if(!(situation & (1<<i))) continue;
        for(int j = 0; j < n; j++){
            // j 번째 발전소 작동시켜줄게요~
            if(!(situation & (1<<j))){
                int nextSitu = situation | (1 << j);
                fix(price + map[i][j], nextSitu);
            }
        }
    }
}

 

 

---

 

힌트를 살짝 보니 DP문제란다. 생각해보니 현재 발전소 상황에서 최소의 비용을 메모이제이션할 수 있을것같다.

그래서 다음과 같이 만들었다.

int memo[1 << 16]; --> 역시나 N이 극도로 작기 때문에 가능. (0번~15번 발전소)

즉, memo[13] 라함은 00001101 의 상황(0번, 2번 발전소 구동중)에서의 최소 비용을 뜻한다.

구동 순서는 상관이 없다 그냥 무조건 작은 비용만을 구하면 된다.

 

// 발전소
// https://www.acmicpc.net/problem/1102
#include <iostream>
#include <cstring>
using namespace std;
const static int INF = 987654321;
int n, p, miniPrice = INF;
int map[16][16];
int memo2[1<<16];

int dp_fix(int situation){
    int &ret = memo2[situation];
    if(ret != -1) return ret;
    
    // base case;
    if(__builtin_popcount(situation) == p){
        return 0;
    }
    
    ret = INF;
    for(int i = 0; i < n; i++){
        // i 번째 발전소 켜져있어야 다른 발전소를 작동 가능.
        if(!(situation & (1<<i))) continue;
        for(int j = 0; j < n; j++){
            // j 번째 발전소 작동시켜줄게요~
            if(!(situation & (1<<j))){
                int nextSitu = situation | (1 << j);
                ret = min(ret, map[i][j] + dp_fix(nextSitu));
            }
        }
    }
    return ret;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> map[i][j];
    string s;
    cin >> s;
    cin >> p;
    
   memset(memo2, -1, sizeof(memo2));
    
    int visited = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'Y'){
            visited |= (1 << i);
        }
    }
    
    int powersCount = __builtin_popcount(visited);
    if(powersCount >= p){
        // 이미 작동하는 발전소가 필요한 수보다 많을 때는 비용이 0.
        cout << 0 << endl;
        return 0;
    }else if(powersCount == 0){
        // 작동가능한 발전소가 없을때는 불가능.
        cout << -1 << endl;
        return 0;
    }
        
    
    int ret = dp_fix(visited);
    if(ret == INF)
        cout << -1 << endl;
    else
        cout << ret << endl;
    
    return 0;
}

 

 

 

시간 지나서 다시 풀어봐야겠다! :)