[백준 1102번] [DP / 비트마스킹] 발전소

Approach

DFS나 BFS를 통해 완전탐색을 하게 되면 시간 초과가 난다. 잘 생각해보면, 현재 켜져있는 발전기의 양상이 동일하면 뒤에 벌어지는 상황도 동일한데, 여러번 계산을 하기 때문에 불필요하게 시간을 많이 소모하게 된다.

 

이 지점에서 DP를 활용하여 켜져있는 발전기의 양상의 상황을 memoization하면 시간 초과를 막을 수 있다는 것을 파악할 수 있다.

 

가장 쉽게 생각할 수 있는 방법은 dp table에 해당 발전기의 양상을 만들기 위해서 필요한 최소 비용을 저장해두는 것이다. 하지만, 특정 상태에서 발전기를 켜는데 최소의 비용이 들었다고 해도, 이후의 발전기가 켜지는 양상에 따라서 더 최소의 비용이 존재할 수 있기 때문에 독립적으로 계산할 수 없기에 계속해서 업데이트를 해주어야 한다. 더욱이 dp식에서 계속해서 종속적으로 엮여있기 때문에 이 방식으로는 풀 수 없다.

 

다른 방법으로는 dp table에 현재 발전기 상태에서 적어도 p개의 발전기가 돌아가기 위한 비용의 최솟값을 저장하는 것이다.

위 방식은 재귀를 통해서 bottom up 방식으로 구현하게 되면 뒤쪽만 바라보면서 일관되게 dp식을 짤 수 있게 된다.

 

dp[visited] = min{dp[to] + cost[i][j]} for j s.t (visited & (1 << j)) == 0 (to = visited | (1 << j) )

 

추가적으로 해당 숫자에 1이 얼마나 켜져있는지 확인하기 위해서 __ builtin_popcount()를 사용해주면 된다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
const int MAX = 987654321;
// 무엇이 켜져있는지 판단하는 것이 가장 중요
int dp[1 << 16];
int n;
int p;
int cost[16][16];

int dp_cal(int visited){
    int& ret = dp[visited];
    if(ret != -1) return ret;
    int t = __builtin_popcount(visited);
    if(__builtin_popcount(visited) == p) return 0;

    ret = MAX;

    for(int i = 0; i < n; i++){
        if(!(visited & (1 << i))) continue;
        for(int j = 0; j < n; j++){
            if(visited & (1 << j)) continue;
            int to = visited | (1 << j);
            ret = min(ret, dp_cal(to) + cost[i][j]);
        }
    }
    return ret;
}

int main(void){
    fastio;
    memset(dp, -1, sizeof(dp));
    cin >> n;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> cost[i][j];
        }
    }

    int vis = 0;
    
    for(int i = 0; i < n; i++){
        char t;
        cin >> t;
        if(t == 'Y') vis |= (1 << i);
    }

    cin >> p;

    // Exception handling
    if(__builtin_popcount(vis) >= p){
        cout << 0 << "\n";
        return 0;
    }
    else if(__builtin_popcount(vis) == 0){
        cout << -1 << "\n";
        return 0;
    }

    cout << dp_cal(vis) << "\n";
    return 0;
}