[BOJ]1102번: 발전소

 

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

---

bitmasking + dp 문제입니다.

 

sungwoo님의 블로그 내용을 참고하여 해결하였습니다. (https://sungwoo91.tistory.com/12)

 

dp테이블은 다음과 같습니다.

 

dp[N][state]: N: 현재 N개의 발전소가 켜져있고, state: N개 중에 어떤 발전소가 켜져있는 상태를 나타냅니다.

 

그리고 dp table에 위와 같은 상태를 만드는데 드는 최소 비용만을 저장해놓습니다.

 

dp[N][state] = minCost

 

그래서 P개를 모두 켰을 때 최소의 비용을 구하면 됩니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1102.cc