BOJ - 발전소(1102)

골드1 : 동적 계획법 문제이다.

생각

dp의 정의는 간단하게 생각할 수 있다. 특정한 상태의 발전소로 오는 방법은 몇가지로 정해지기 때문이다. 그래서 정의를 잡으면 다음과 같다.

정의

dp[상태] = 발전소의 상태에서의 발전소를 고치는데 발생하는 비용의 최솟값

그렇다면 상태는 어떻게 정의할 수 있을까?

비트마스크

YNN은 100으로 생각할 수 있다. 그렇다면 이 상태에서 다음상태로는 어떻게 갈 수 있을까?

1. 켜져있는 발전소를 확인한다.
2. 해당 발전소에서 꺼져있는 발전소를 확인한다.
3. 꺼져있는 발전소를 킨다.
4. 다른 상태에서 또 같은 상태로 올 때, 최소값으로 업데이트 한다.

주의할 점

초기값을 모두 -1로 만든 상태에서 값을 출력하는 것이 좋다. 만들지 못하는 경우를 출력하기 위함이다. 또한 0개의 발전소를 키라는 조건에서 -1을 리턴하면 안되고 0을 리턴해야 한다.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int N;
int a[17][17];
string str;
int dp[1<<16];
int p;
 
int main(){
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> a[i][j];
        }
    }
    int start = 0;
    for (int i = 0; i < N; i++) {
        char temp;
        cin >> temp;
        if (temp == 'Y') start += (1<<i); // YNN -> 001로 저장한다. 이진수의 shift연산 중에는 이게 편하다.
    }
    cin >> p;
 
    // 기본 dp의 값을 -1로 해둔다.
    // 일단 다 못 만든다고 가정하는 것
    memset(dp, -1, sizeof(dp));
    dp[start] = 0;    //  start에서 dp값은 0이다. 최소값이 0
    for (int i = 0; i < (1<<N); i++) {
        if (dp[i] == -1) continue; // 상태에 대한 최소값이 없다면 진행할 수 없다.
        for (int j = 0; j < N; j++) {   // 발전소를 순차적으로 체크하며 다음 상태를 만든다.
            if (i&(1<<j)){    // 현재 발전소의 상태중 j번째 발전소가 있다면
                for (int k = 0; k < N; k++) {
                    if ((i&(1<<k)) == 0){   // 현재 발전소의 상태에서 j번째 발전소를 가지고 k위치의 발전소를 키려고 할때 k위치 발전소가 꺼져있다면
                        if (dp[i|(1<<k)] == -1 || dp[i|(1<<k)] > dp[i] + a[j][k]) {
                            dp[i|(1<<k)] = dp[i]+a[j][k];
                        }
                    }
                }
            }
        }
    }
 
    int ans = -1;
    for (int i = 0; i < (1<<N); i++) {
        if (dp[i] == -1) continue;
        int count = 0;
        for (int j = 0; j < N; j++) {
            if (i&(1<<j)) count++;
        }
        if (count >= p) {
            if (ans == -1 || ans > dp[i]) ans = dp[i]; // ans를 -1로 했기 때문에 처음에 scope들어오기 위해 조건 추가
        }
    }
    cout << ans << '\n';
}

Reference

• 백준(1102번) - 발전소