문제링크
문제
은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다.
발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다.
적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 값이다. 그 다음 줄에는 각 발전소가 켜져있으면 Y, 꺼져있으면 N이 순서대로 주어진다. 마지막 줄에는 P가 주어진다. 비용은 50보다 작거나 같은 음이 아닌 정수이고, P는 0보다 크거나 같고, N보다 작거나 같은 정수이다.
풀이 유형
풀이
N이 16 이하의 자연수이다. 수가 32 이하라면 비트마스크 문제가 아니어도 왠지 비트마스크로 풀고 싶어진다. 다행이도 이 문제는 비트마스크로 풀이가 가능하다. 이 문제의 풀이는 거두절미하고 비트마스크를 이용한 동적 계획법이다. 풀이는 아래와 같다.
1
2
3
4
// n은 원래 상태에서 도달 가능한 상태를 저장한 bit
// i는 0 부터 N-1까지
// a는 n에서 a번째 발전소가 켜져 있는 모든 a
dp[n|(1<<i)] = min(dp[n|(1<<i)], dp[n] + cost[a][log2(i)])
다소 머리가 아플 수 있는데, 예시를 생각해보면 쉽게 이해가 간다.
여기, YNNYN 이런 상태의 발전소가 주어진다. 우리는 이 상태를 10010으로 표기한다. 여기서 우리는 4개 이상의 불을 키고 싶다. 그렇다면 어떻게 해야하는가?
우리는 00000 부터 11111 까지 루프문을 통해 모두 탐색한다. 10010이 되기 전까지 모든 수는 원래 상태에서 도달이 불가능하다. 왜냐하면 우리는 불을 끄는 선택지가 없으니까. 00000, 00001, 00010,..,10001 모두 무시한다.
자 우리는 쓸 모 없는 수들을 지나 10010에 도달했다. 우리는 이제 11010, 10110, 10011의 세 상태에 대하여 현재 상태에서 최저로 해당 상태들로 도달할 수 있는 값들을 업데이트 할 것이다. (11010, 10110, 10011은 원래 상태 10010에서 0을 하나만 1로 바꾼 경우들이다.)
기존에 10010이었으니 우리는 0번째, 3번째 발전소가 켜져있음을 알 수 있다. 우리는 이 두 발전소 중 하나 씩 골라 11010, 10110, 10011을 만드는 제일 싼 값을 골라 해당 dp배열에 저장하면 되는 것이다. 어차피 bit를 올린다는 것은 값을 더해준다는 의미이기 때문에 00000부터 11111까지 실행하면, 논리적 오류는 발생하지 않는다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i=0; i < (1<<N); i++){
// (비트 수에 따라 다름)
// 00...00부터
// 11...11까지
if(dp[i] == MAX) continue; //MAX란 것은 도달이 불가능한 비트를 의미함.
for(int j=0; j < N; j++ ){ // j는 새로 킬 발전소의 index
if((1<<j) & i) continue; // 이미 켜진 발전소라면 continue
for(int k=0; k<N; k++){ // k는 이미 켜진 발전소의 index
if( ((1<<k) & i) == 0) continue; // 꺼진 발전소라면 continue
dp[i|(1<<j)] = min(dp[i|(1<<j)], dp[i] + board[k][j]); // 계산
}
}
if(count(i) >= P){ // ! 주의 등호로 하면 틀림
if(anw > dp[i]) anw = dp[i];
}
}
마무리
본인은 비트수를 계산하는 부분에서 예외처리를 실패하여, 무수한 실패를 조우해야 했다. count(i)는 켜져야 하는 발전소의 개수 P개 보다 크거나 같으면 된다는 것을, 처음에 어차피 비트 연산 이후의 값은 이전의 값보다 클 수 밖에 없다는 생각으로 대충 넘겼다가 피봤다. 애초부터 켜진 발전소가 P개보다 큰 경우를 생각치 않은 것이다. 그 외에 모두 꺼져 있는 경우, 그냥 -1을 출력했다가 또 틀렸다. 모두 꺼져 있더라도 P가 0이면 -1이 아닌 것이다. 다시 한 번 예외 처리의 중요성을 절감하게 되는 문제였다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#define Min(X, Y) ((X) < (Y) ? (X) : (Y))
#define Max(X, Y) ((X) > (Y) ? (X) : (Y))
#define MAX 2100000000
using namespace std;
int N;
int board[16][16];
int cost[16];
int bit = 0;
int P;
int on = 0;
int anw = MAX;
int dp[66000];
int count(int n){
int ret = 0;
for(int i=1; i < 1<<N; i = i<<1){
if(i & n) ret += 1;
}
return ret;
}
int main(void){
scanf("%d",&N);
for(int i=0; i<66000; i++){
dp[i] = MAX;
}
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
int n; scanf("%d", &n);
board[i][j] = n;
}
}
int on = 0;
for(int i=0; i<N; i++){
char c; cin>>c;
if(c == 'Y') {
on++;
bit = bit|(1<<i);
}
}
dp[bit] = 0;
scanf("%d",&P);
for(int i=0; i < (1<<N); i++){
if(dp[i] == MAX) continue;
for(int j=0; j < N; j++ ){
if((1<<j) & i) continue;
for(int k=0; k<N; k++){
if( ((1<<k) & i) == 0) continue;
dp[i|(1<<j)] = min(dp[i|(1<<j)], dp[i] + board[k][j]);
}
}
if(count(i) >= P){
if(anw > dp[i]) anw = dp[i];
}
}
if(bit==0 && P != 0) anw = -1;
cout<<anw<<endl;
return 0;
}