-
[BOJ/python]1102번 발전소알고리즘/BOJ 2022. 7. 6. 22:55
백준 1102번 발전소 파이썬
문제 링크 -https://www.acmicpc.net/problem/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)
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ/python]15681번 트리와 쿼리 (0) 2022.07.06 [BOJ/python]3860번 할로윈 묘지 (1) 2022.07.06 [BOJ/python]1182번 부분수열의 합 (0) 2022.07.06 [BOJ/python]10282번 해킹 (0) 2022.07.06 [BOJ/python]1162번 도로포장 (0) 2022.07.06