발전소

백준 1102번: 발전소

아이디어

외판원 순환 문제보다 살짝 단순하다. 현재 상태에서 적어도 P개의 발전소가 돌아가기까지 필요한 최소 비용을 메모이제이션 하면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

const int INF = 987654321;
int N, P, start = 0, ans = INF;
int arr[16][16];
int cache[1<<16];

int solve(int visited) {
    int cnt = __builtin_popcount(visited);
    if (cnt >= P) {
        return 0;
    }
    
    int &ret = cache[visited];
    if (ret != -1) return ret;
    
    ret = INF;
    
    for (int i = 0; i < N; i++) {
        if (!(visited&(1<<i))) continue;
        for (int j = 0; j < N; j++) {
            if (visited&(1<<j)) continue;
            ret = min(ret, solve(visited|(1<<j)) + arr[i][j]);
        }
    }
    
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
    string s;
    cin >> s;
    for (int c = 0; c < s.size(); c++) {
        if (s[c] == 'Y') {
            start |= (1<<c);
        }
    }
    cin >> P;
    memset(cache, -1, sizeof(cache));
    ans = solve(start);
    if (P == 0) cout << 0;
    else if (ans == INF) cout << -1;
    else cout << ans;
    return 0;
}

여담

얘도 그렇고 외판원 순회도 그렇고 탑다운 dp로 풀면 좀 더 직관적으로 풀 수 있다. 많이 짜서 탑다운 모양을 익혀야겠다.