이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 18 번째 글 입니다.
목차
골드1 : 동적 계획법 문제이다.
생각
dp의 정의는 간단하게 생각할 수 있다. 특정한 상태의 발전소로 오는 방법은 몇가지로 정해지기 때문이다. 그래서 정의를 잡으면 다음과 같다.
정의
dp[상태]= 발전소의 상태에서의 발전소를 고치는데 발생하는 비용의 최솟값
그렇다면 상태는 어떻게 정의할 수 있을까?
비트마스크
YNN은 100으로 생각할 수 있다. 그렇다면 이 상태에서 다음상태로는 어떻게 갈 수 있을까?
- 켜져있는 발전소를 확인한다.
- 해당 발전소에서 꺼져있는 발전소를 확인한다.
- 꺼져있는 발전소를 킨다.
- 다른 상태에서 또 같은 상태로 올 때, 최소값으로 업데이트 한다.
주의할 점
초기값을 모두 -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';
}