1102. 발전소

1102번: 발전소

---

최소의 비용으로 적어도 p개의 발전소를 켜야 하는 문제이다.

 

문제를 풀기 전에 짚고 넘어가야 할 점이 있다.

1. 발전소를 동시에 켜는 것이 아니며, 이전에 켠 발전소로 다른 발전소를 켤 수 있다.

2. 발전소를 켜는 비용은 0일 수도 있다. 

3. 정확히 p개를 켜는 것이 최적이 아닐 수도 있다. 왜냐하면 처음에 이미 p개 이상의 발전소가 켜져 있을 수도 있기 때문이다.

4. 섣불리 -1을 출력하면 틀렸습니다. p가 0일 수도 있다.

 

 

문제를 정확히 이해했다면 이제 풀이를 고민해 보자. 

어떤 발전소를 어떤 순서로 켜야 할까?

주목할 점은 N이 최대 16이라는 것이다. 문제에서 N이 매우 작을 때는 항상 완전 탐색이 가능한지 의심해야 한다. 이 문제에서는 발전소의 상태가 최대 2^16가지이므로, 시간 안에 완전 탐색이 가능하다.

 

발전소의 상태는 어떻게 저장해야 할까? boolean 배열 16개로 할 수도 있겠지만, 비트마스크를 이용하여 단 2바이트로 상태를 저장할 수 있다. 켜져 있는 발전소로 꺼져 있는 다른 발전소를 모두 켜 보면서 최솟값을 찾으면 된다. 

 

물론 중복 탐색을 방지하기 위해 dp 배열에 값을 저장하자. 이때 배열을 0으로 초기화하면 안 된다. 이해가 되지 않는다면 위의 2번을 다시 읽어보자.

---

문제의 질을 올리자.