[백준] No.1102 - 발전소 (C++, 비트마스크)
문제
https://www.acmicpc.net/problem/1102
1102번: 발전소
은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이
www.acmicpc.net
풀이
solved.ac 난이도: Gold 1
비트마스크와 다이나믹 프로그래밍을 이용하는 문제.
두 가지를 기법을 조합하는 문제다 보니 두 기법을 잘 안다면 난이도에 비해 어렵진 않지만
개인적으로는 한 가지 예외를 발견하기가 힘들었다.
해당 문제에서는 발전소가 켜져 있는 상태는(1), 꺼져있는 상태는(0) 비트로 나타낸다.
단순히 생각하면 켜져있는 발전소들로 꺼져있는 발전소를 재시작할 때의 최소 비용들을 모두 구해 더하면 된다고 생각할 수 있다.
하지만 j 발전소를 재시작하면, j로 다른 발전소를 재시작할 수 있게 상태가 바뀌기 때문에
모든 발전소 상태를 방문해 최솟값을 찾는 다이나믹 프로그래밍으로 문제를 해결하였다.
int TurnOnStation(int turned_num, int state)는 켜져있는 발전소의 수(turned_num), 비트형식으로 나타낸 발전소들의 상태 state를 이용해 P 이상의 발전소를 켜는 최솟값을 반한다.
만약 j번째 발전소가 꺼져있는 지 확인하고 싶다면,
if( ~state & (1<<j) )를 확인하면 된다.
꺼져있는 j번째 발전소를 찾았다면 켜져 있는 발전소들에서 최솟값으로 j를 재시작할 수 있는 min_cost값을 찾는다.
이제 변화한 발전소의 상태는 j번째 비트를 키는 것으로 나타낼 수 있다. => state | (1<<j)
따라서 현재 state를 토대로 꺼져있는 발전소를 최소비용으로 키고 TurnOnStation를 재귀 호출하면서
기저사례, turned_num >= P(적어도 켜져있어야 하는 발전소 수)까지 계산하면 된다.
cache[state] = min(cache[state], TurnOnStation(turned_num+1, state|(1<<j) ) + min_cost );
처음 구현할 때는 cache를 cache[16][(1<<16 )-1]로 선언하여
cache[turned_num][state]를 저장하려 했는데 사실 이미 state값에는 몇 개의 발전소가 켜져 있는지에 대한 정보가 담겨있으므로
cache는 cache[1<<16 )-1]만으로도 충분하다.
추가적으로
N개의 발전소의 상태가 모두 꺼진 상태로 주어진다면 다른 발전소를 재시작할 수 없기 때문에
불가능할 때의 비용 값 -1을 출력해주어야 한다.
그리고 발전소가 모두 꺼져있더라도 켜져있어야 하는 발전소의 개수 P가 0이라면 불가능한 경우가 아니다!
따라서 비용 값은 0을 출력해준다.
코드
#include <iostream> | |
#include<string.h> | |
#include<string> | |
using namespace std; | |
const int MAXN = (1<<16 )-1; | |
int station_num; | |
int start_cost[16][16]; | |
int least_num; | |
int cache[MAXN]; | |
int TurnOnStation(int turned_num, int state){ | |
if(turned_num>= least_num) | |
return 0; | |
int& ret = cache[state]; | |
if(ret != -1) | |
return ret; | |
ret = 800; | |
int min_cost= 51; | |
for(int j =0; j <station_num ; ++j){ | |
if( ~state & (1<<j) ){ //j번째 발전소가 꺼져있는 경우(0인 경우) | |
for(int i=0; i<station_num ; ++i){ | |
if(state & (1<<i)) //i번째 발전소가 켜져있는 경우(1인 경우) | |
min_cost = min(min_cost, start_cost[i][j]); | |
} | |
ret = min(ret, TurnOnStation(turned_num+1, state|(1<<j) ) + min_cost); | |
min_cost = 51; | |
} | |
} | |
return ret; | |
} | |
int main() { | |
string st; | |
int station_state=0,turned_on=0; | |
cin>>station_num; | |
for(int i=0; i<station_num ; ++i) | |
for(int j=0; j<station_num ; ++j) | |
cin>>start_cost[i][j]; | |
cin>>st>>least_num; | |
for(int i=0; i<station_num ;++i){ | |
if(st[i] =='Y'){ | |
station_state |= (1<<i); | |
++turned_on; | |
} | |
} | |
if(station_state ==0){ | |
if(least_num ==0) | |
cout<<"0\n"; | |
else | |
cout<<"-1\n"; | |
return 0; | |
} | |
memset(cache, -1, sizeof(cache)); | |
cout<<TurnOnStation(turned_on, station_state)<<"\n"; | |
return 0; | |
} |