개구리의 개발 블로그 개구리의 개발 블로그

백준 1102번 발전소 파이썬 문제 링크 -https://www.acmicpc.net/problem/1102 1102번: 발전소 첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 www.acmicpc.net 오랜만에 재밌는 DP 문제였다. 처음에는 문제를 보자마자 백트래킹으로 풀어야겠다고 생각했다. 그런데 생각해보면 A발전소를 고칠 수 있는 모든 발전소에 대한 경우를 탐색하기 때문에 가지치기가 불가능한 상황이다. 현재 상황에서 정상 작동하고 있는 모든 발전소가 A개이고 정상 작동하지 않는 모든 발전소가 B개라면 총 A*B개의 발전소를 고치는 조합이 존재한다..