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

문제

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

1102번: 발전소

 

 

풀이

 

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을 출력해준다.

 

코드