#1102 발전소

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

1102번: 발전소

비트마스킹와 메모이제이션을 활용한 문제

 

켜져있는 발전소들을 기준으로 계속해서 꺼져있는 발전소을 가동시켜야 하는 문제이며 꺼져있던 발전소가 켜지게 된다면 그 발전소로도 다른 발전소들을 가동시키는 것이 가능해진다.

 

재귀를 활용한 메모이제이션을 적용하였고 점화식과 종료조건은 다음과 같고 메모를 활용하기 위한 dp배열은

dp[가동시킨 공장 수][ 어떤 공장들을 켰는지 (비트마스킹으로 )]표현 하였다.

 

점화식

 

n개의 발전소를 가동시키는데에 든 비용 = MIN(n개의 발전소를 가동시키는 데에 든 비용 or (n-1)개까지 가동시키는 데에 든 비용 + 현재 켜야할 발전소 비용)

 

종료조건

 

켜져있는 발전소(cnt)가 p개 이상이면 종료한다.

이미 가동 시켰던 공장이면 (방문했던곳이면) 메모를 해둔다.

 

소스코드