[1102] 발전소

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

처음엔 on과 off인 부분을 나눠서

그리디로 접근을 하려고 했었는데

1-2로 가는데 5, 2-3으로 가는데 20

1-4로 가는데 10, 4-5로 가는데 5이고, YNNNN, p = 3이라면

1-4-5 루트가 나와야하는데 1-2-3 루트가 나옵니다.

짱돌을 엄청나게 굴렸지만.... 생각이 잘안났습니다.

그래서 분류를 봤는데

dp와 비트마스크로 해결하는 문제였습니다.

저는 2차원 dp로 해결했습니다.

dp[on 발전소 갯수][발전소의 상태]라고 정의했습니다.

사실 발전소의 상태로 발전소의 개수를 알 수 있지만 편의를 위해 이렇게 해결했습니다.

문제에서 적어도 p개라고 했는데 p개 초과일 경우가 p개인 경우보다 코스트가 작아지는 경우는 없으므로

탈출조건은 발전소 갯수가 p이상일 때 탈출시켰습니다.

아래는 코드입니다.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stack>
#include <string>
 
#define ll long long
#define INF 987654321
#define MOD 1000000
#define MAX_SIZE 16
#define mp make_pair
#define pii pair<int, int>
using namespace std;
 
int spend[MAX_SIZE][MAX_SIZE];
int dp[MAX_SIZE][1 << 16];
int n, p;
int on;
int onCnt;
 
int f(int cnt, int on) {
    if (cnt >= p) return 0;
 
    int &ret = dp[cnt][on];
    if (ret != -1) return ret;
    ret = INF;
 
    for (int i = 0; i < n; i++) {
        if(on & 1 << i){
            for (int j = 0; j < n; j++) {
                if (i == j || on & (1 << j)) continue;
                ret = min(ret, f(cnt + 1, on | 1 << j) + spend[i][j]);
            }
        }
    }
 
    return ret;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> spend[i][j];
        }
    }
 
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        if (c == 'Y') on |= 1 << i, onCnt++;
    }
 
    cin >> p;
 
    memset(dp, -1, sizeof(dp));
 
    int ret = f(onCnt, on);
    cout << (ret == INF ? -1 : ret);
 
    return 0;
}