알고리즘 공부/백준

[백준] No.1102 - 발전소 (C++, 비트마스크)

EVEerNew 2021. 1. 18. 20:10
반응형

문제

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;
}

 

반응형