https://www.acmicpc.net/problem/25048
문제요약
- N개의 스위치, M개의 PC, 스위치는 포트(a)와 비용(b)이 있음
- 외부 인터넷선은 하나
- M개의 PC가 모두 인터넷이 되어야함 && 남는 포트가 없어야함
- 가능할 때 최소 비용
- N : 300, M : 10^5, a : 10^5, b : 10^9
접근법
- N과 M이 크지 않은 숫자임
- x개의 스위치로 구성을 완료했을때 M = 포트의합(x) - (2 * x-1) 를 만족하는 방식으로 접근하려했는데 잘 안됨
- (1...p)까지의 스위치로 q개의 포트를 채울때의 최소 비용으로 접근해봄
- q개의 포트를 채우기 위해서 q - (스위치의 포트 - 2)개를 채운 경우를 참고
- 연결하려는 스위치 각각에서 포트를 사용해야 케이블이 연결되므로
- 처음에 인터넷 연결할때는 예외 처리 : 스위치 포트 - 1 처리
- 예외사항
- 스위치의 포트가 1개일때는 처리하지 않음
- 인터넷 선이 PC에 바로 연결 되는 경우 예외 이때는 항상 비용이 0
newbieski