[BOJ/python]1102번 발전소

백준 1102번 발전소 파이썬

문제 링크 -https://www.acmicpc.net/problem/1102

1102번: 발전소

오랜만에 재밌는 DP 문제였다. 처음에는 문제를 보자마자 백트래킹으로 풀어야겠다고 생각했다. 그런데 생각해보면 A발전소를 고칠 수 있는 모든 발전소에 대한 경우를 탐색하기 때문에 가지치기가 불가능한 상황이다.

 

현재 상황에서 정상 작동하고 있는 모든 발전소가 A개이고 정상 작동하지 않는 모든 발전소가 B개라면 총 A*B개의 발전소를 고치는 조합이 존재한다. 이 경우를 모두 탐색하며 최소 비용으로 매번 갱신해야 하는데 DP를 이용하면 된다.

 

DP점화식의 경우 생각보다 떠올리기 쉬웠다. 백준 2001번 보석줍기 문제가 비트마스킹을 이용하는 DP문제를 해결할 때 좋은 참고가 되는 것 같다. (https://www.acmicpc.net/problem/2001)

1. DP 점화식

base case에서부터 생각해보자. 가장 초기에 켜진 발전소의 개수가 X개라면 이를 위해서는 비용 0이 필요하다. DP의 메모리를 아끼기 위해서 켜진 발전소를 0개부터 모든 경우를 저장하지 않고 앞으로 고쳐야 할 발전소의 개수를 기준으로 생각해보자.

즉 base case는 초기에 주어진 발전소의 상태에서 추가적으로 고친 발전소의 개수가 0개인 경우다.

• dp[0][status] = 초기 상태보다 0개의 발전소를 더 고치고 status의 상태가 된 경우의 최소 비용
• dp[1][newStatus] = 초기 상태보다 1개의 발전소를 더 고치고 newStatus의 상태가 된 경우의 최소 비용
• dp[1][newStatus] = dp[0][status] + (status에서 newStatus로 가기 위한 비용들 중 최소)
• status에서 newStatus로 가기 위한 최소 비용을 반복문을 통해 갱신하면 된다.
• 만약 dp[1][newStauts]가 이미 갱신된 경우라면 위의 값과 이미 갱신된 값 중 더 작은 값을 저장한다.
• 즉 dp[p-1][status]가 갱신되어 있다면 dp[p][newStatus] = min(dp[p-1][status] + cost, dp[p][newStatus])로 표현할 수 있다. (dp[p][newStatus]가 갱신되지 않은 경우라면 비교하지 않고 저장)

2. 풀이

• 현재 상태를 비트마스크로 표현한다. 3차원 배열로 dp를 만들 수도 있지만 메모리 초과가 발생할 수 있으므로 비트로 표현한다.
• 현재 켜진 발전소의 개수를 count에 저장하고 더 고쳐야하는 발전소의 개수를 toSet에 저장한다. 이를 이용하여 문제 해결이 불가능하거나 더 고칠 필요가 없는 경우에는 프로그램을 종료한다.
• 모든 N자리 이진수에 대하여 탐색하며 해당 이진수가 dp에 갱신된 경우에만 다음 단계의 dp를 갱신한다. 즉 p개의 발전소를 추가로 켜졌을 때 bitStat가 불가능한 경우라면 반복문을 실행하지 않는다.
• bitStat에서 1로 표현된 발전소를 idx로 0으로 표현된 발전소를 next로 하는 모든 조합에 대하여 반복문을 실행한다. idx발전소로 next발전소를 고치기 위한 비용이 G[idx][next]이다.
• 고쳐야 하는 발전소의 개수 toSet개 까지 모두 갱신한 뒤 최소 비용을 출력한다.

3. 코드

G = []
#입력값 받기
N = int(input())
for _ in range(N):
    G.append(list(map(int, input().split())))
status = input()
P = int(input())

#상태 비트로 표현하기
firstStat = 0

count = 0
#YNN이면 001
for i in range(N):
    if status[i]=='Y' :
        firstStat |= 1<<(i) 
        count+=1
        
toSet = P-count
if toSet <=0 :
    print(0)
    quit()
elif count == 0:
    print(-1)
    quit()

dp = [ [ -1 for _ in range(2**N) ] for _ in range(toSet+1)]
dp[0][firstStat] = 0

for bitStat in range(firstStat, 2**N):
    
    for p in range(1,toSet+1):    
        
        if dp[p-1][bitStat] != -1:
            
            for idx in range(N) :
                if bitStat & 1<<idx == 1<<idx : 
                    
                    
                    for next in range(N):
                        if next!=idx and bitStat & 1<<next != 1<<next:
                        # if next!=idx:
                            
                            newStat = bitStat | 1<<next
                            cost = G[idx][next]
                            
                            if dp[p][newStat] == -1 :
                                dp[p][newStat] = dp[p-1][bitStat] + cost    
                            else:
                                dp[p][newStat] = min( dp[p][newStat], dp[p-1][bitStat] + cost   )

answer = float('inf')  
for i in range(2**N):
    if dp[toSet][i] != -1:
        answer=min(dp[toSet][i] , answer)
print(answer)