백준) 1102 발전소

1102. 발전소

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

문제

은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다.

발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이 때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다.

적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 값이다. 그 다음 줄에는 각 발전소가 켜져있으면 Y, 꺼져있으면 N이 순서대로 주어진다. 마지막 줄에는 P가 주어진다.. 비용은 50보다 작거나 같은 음이 아닌 정수이고, P는 0보다 크거나 같고, N보다 작거나 같은 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 

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

예제 출력 

21

1. 접근

p개 이상의 발전소를 규칙에 따라 모두 가동시켜야 한다.

발전소를 가동시킬려면 기존에 가동되고 있던 발전소가 필요하고, 발전소끼리 가동시키는 비용이 각기 다르다.

p개 이상의 발전소를 가동시키는데 드는 총 비용의 합이 최소가 되는 경우는 무엇일까?

2. 풀이

p개 이상이란 뜻을 생각해보자.

p + 1, p + 2, ... n 개를 가동시키는데 드는 최소비용이 p개 보다 작을 경우가 있다는 말일까?

있다고 쳐보자, 그러면 p + x 개를 가동시키는 방법은 p개를 가동시키는 방법과 다른 부분이 존재한다는 뜻이다.

완전한 부분집합이라면 당연히 p개가 더 작다.

하지만 다른 부분으로 이어지는 경로의 p개 까지의 경로가 당연히 p + x 보다 짧다!

따라서 우리는 문제를 괜히 꼬아서 낸거라고 생각하고 p개로 고정시키자.

일단 -1을 출력해야 하는 상황을 생각해보자면,

하나라도 켜져 있으면 전부 가동시킬 수 있으니까, 전부 고장난 상태라면 -1이다.

마찬가지로 이미 p개보다 많이 켜져있다면 보나마나 0이다.

한편 이 문제를 그리디적으로 풀 수 있을까?

당장에 가동중인 발전기로 가동시킬 최소비용을 선택해 나가는 것이다.

하지만 최소비용이 같을 경우, 나머지 부분 문제는 당연히 가동중인 발전기 종류가 달라지므로 그리디적으로 풀 수 없다.

그러면 다 계산해보자!

n개의 발전기가 있으므로, 각 발전기가 가동중인 상태를 비트로 나타내기 위해선 n + 1 개의 비트가 보장되어야 한다.

그러면 DP[2 ^ N]의 배열을 잡자. 이 배열은 현 가동 상태에서 추가로 발생하는 비용을 담는다.

우리의 답은 DP[처음의 가동 상태]에 있을 것이다.

이제 계산을 해줄 함수를 정의해보자.

func(int num, int stat) = num개를 가동 중이고, 가동상태는 비트로 stat일때, 추가로 발생하는 비용

계산식을 어떻게 만들어야 할까?

n=3이고 현 상태가 100이라 해보자(1발전기가 가동중이다)

먼저 가동중인 발전기를 찾아야 한다. 그 다음으로 고장난 발전기를 찾아야한다.

이 후 가동시키려면 당장의 비용이 발생하니까, 식은 다음과 같다.

dp[stat] = min(dp[stat], func(num + 1, stat | (1 << 고장난 발전기)) + cost[가동 발전기][고장 발전기]

기저사례는 num이 p까지 도달해버린 경우로, func(p, stat) 은 당연히 정의에 따라 0을 반환해야 한다.

메모이제이션을 통해 시간이 단축된다.

3. 코드

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <algorithm>
using namespace std;
 
int n, p, i, j, cur, full;
int cost[16][16];
int dp[1 << 16];
char str[17];
 
int func(int num, int stat) {
    if (num == p)
        return 0;
 
    int& ref = dp[stat];
    if (ref != -1)
        return ref;
 
    ref = INT_MAX;
 
    for (int from = 0; from < n; ++from) {
        if (stat & (1 << from)) {
            for (int to = 0; to < n; ++to) {
                if (from == to)
                    continue;
 
                if ((stat & (1 << to)) == 0)
                    ref = min(ref, func(num + 1, stat | (1 << to)) + cost[from][to]);
            }
        }
    }
 
    return ref;
}
 
int main() {
    memset(dp, -1, sizeof(dp));
 
    scanf("%d", &n);
 
    full = (1 << n) - 1;
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            scanf("%d", &cost[i][j]);
 
    scanf("%s %d", str, &p);
 
    int cnt = 0;
    for (i = 0; i < n; ++i) {
        if (str[i] == 'Y') {
            cur = cur | (1 << i);
            cnt++;
        }
    }
 
    if (cnt == 0) {
        if (p == 0)
            puts("0");
        else
            puts("-1");
    }
    else if (cnt >= p)
        puts("0");
 
    else
        printf("%d", func(cnt, cur));
 
    return 0;
}

4. 후기

메모이제이션을 이상하게 해서 한참을 해맸다. 기초의 중요성 ㅎ