1102번 - 발전소

해결방법

해당 문제는 bitmask dp로 풀었다. bit가 켜지면 발전소가 켜진 것이고, bit가 꺼지면 발전소가 꺼진 것이다. bitmask dp로 푼 이유는 a번째 발전소가 j번째 가동시킬때와 b번째 발전소가 j번째 발전소를 가동시킬때가 다르기 때문이다. 문제를 풀 때 유의할 점은 0개 이상일 경우이다. 0개 이상일 경우 0을 리턴해야하지 -1를 리턴하게 하면 안된다.

int dp[1 << 16]
int N : 발전소의 개수
int T : 켜져있어야할 최소 발전소
int s : 켜진 발전소의 번호를 비트 마스크로 표현
int lab[16][16] : i번째 발전소가 j번째 발전소를 가동시키는데 필요한 비용

아래는 변수의 대한 설명이다. 재귀방식으로 풀었고, 생각보다 어렵지는 않았다. 먼저 기저사례로 켜져있는 비트 수가 T보다 크다면 0을 리턴하도록 하였다.

for (int i = 0; i < N; ++i)
    if ((s >> i) % 2 == 1)
        cnt++;
if (cnt >= T) return 0;

T보다 작다면 비트가 0인 수를 찾은 다음 비트가 1인 수들 중에서 비용 값을 더해주고 0비트를 1로 바꿔 재귀시켜준다.

    for (int i = 0; i < N; ++i) {
        if ((s >> i) % 2 == 0) { // 안켜진 발전소 찾기
            for (int j = 0; j < N; ++j)
                if ((s >> j) % 2 == 1) // 켜진 발전소 찾기
                    ret = min(ret, solution(s | 1 << i) + lab[j][i]); // j발전소에서 i발전소를 킨 경우 비용 더해줌.
        }
    }

전체코드

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[1 << 16], N, T;
int lab[17][17];
const int INF = 801;
int solution(int s) {
    int cnt = 0;
    for (int i = 0; i < N; ++i)
        if ((s >> i) % 2 == 1)
            cnt++;
    if (cnt >= T) return 0;
    int& ret = dp[s];
    if (ret != -1) return ret;
    ret = INF;
    for (int i = 0; i < N; ++i) {
        if ((s >> i) % 2 == 0) {
            for (int j = 0; j < N; ++j)
                if ((s >> j) % 2 == 1)
                    ret = min(ret, solution(s | 1 << i) + lab[j][i]);
        }
    }
    return ret;
}
int main() {
    memset(dp, -1, sizeof(dp));
    cin >> N;
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < N; ++x)
            cin >> lab[y][x];
    int s = 0;
    for (int i = 0; i < N; ++i) {
        char c;
        cin >> c;
        if(c == 'Y')
            s |= (1 << i);
    }
    cin >> T;
    int ret = solution(s);
    if (ret == INF)
        cout << -1 << endl;
    else cout << ret << endl;
    return 0;
}