[백준 / BOJ] 1102 발전소

문제

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

1102번: 발전소

은진이의 회사에는 N개의 발전소가 있다.

은진이가 회사에서 잘때마다 몇몇 발전소가 고장이난다. 

이때, 고장난 발전소는 고장나지않은 발전소를 이용해 고칠수있으며, 일정한 비용이 발생한다.

적어도 P개 이상의 발전소가 고장나 있지 않도록 발전소를 고치는 최소비용을 구하는 문제다.

 

풀이

dp로 풀은문제다.

그리디로는 해결하지못하는데, 현재 경로가 더 많은 비용을 필요로 하더라도 결과적으로 더 작은 비용으로 발전소를 수리할수있기 때문이다. (현재 최소 경로가 끝까지 최소경로가 아닐수있음) 

따라서, 모든 경우를 다이나믹 프로그래밍을 이용해 빠르게 봐주며 문제를 해결해야한다.

 

발전소가 최대 16개이니, 비트마스킹을 이용해 발전소의 현재상태를 체크해줄수있다.

ex) 0000 0000 0000 0010 => 1번발전소가 정상임 (0번은 비워놨다)

 

N = 4 일때, 현재 발전소 상태를

1111 이라고 하자. (1,2,3,4 발전소가 정상임)

위의 상태를 만들기 위해선 다음 경로를 봐줘야한다.

1. 1110 (1,2,3 발전소가 정상임)

2. 1101 (1,2,4 발전소가 정상임)

3. 1011 (1,3,4 발전소가 정상임)

4. 0111 (2,3,4 발전소가 정상임)

즉, 위에서부터 1,2,3,4번 발전소를 고치는경우중 최솟값을 가져오면된다.

이때, 고장난 발전소 A(i) 를 고치는 최솟값은 발전소 A(1~N)를 이용해 A(i)를 고치는값중 최솟값을 가져오면된다.

 

예외처리를 안해줘서 틀렸었는데,

1. P가 0인 경우, 고장나지않은 발전소의 갯수는 항상 P 이상이므로, 비용은 0이다.

2. 켜져있는 발전소가 0 개이며 P가 0보다 클경우 어떤 발전소도 더 이상 킬수없으므로, -1이 출력되야한다.

 

구현은

- 우선, 모든 비트를 초기화시켜준다.

1. 우선 만들수있는 모든 최종 상태를 만들어준다. (NCP)개

2. 모든 최종상태에서 시작하며, 고장나있지 않은 발전소를 하나씩 고장낸다. 이때, 현재 고장낸 발전소를 고치는데 필요한 비용을 더해준다.

3. 위 과정을 바텀업으로 구현했다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1102%20%EB%B0%9C%EC%A0%84%EC%86%8C/main.cpp

devxb/JJUNalgo