[BOJ 2365] 숫자판 만들기

문제 출처 : https://www.acmicpc.net/problem/2365

2365번: 숫자판 만들기

 

풀이 :

 

네트워크 플로우 최대 유량 문제입니다.

 

아래의 그림 처럼 행과 열을 각 각 묶어서 모델링 하여

1번행 3번열을 묶으면 (1,1),

1번행 4번열을 묶으면 (1,2)

이런식으로 표현 될 수 있도록 모델링 합니다.

그 후 문제 조건에 따라 최대 숫자의 값을 최소로 하는 형태를 찾아야합니다.

이는 모든 엣지의 Capacity에 대해 Limit을 1 ~ 1000까지 걸어

이분탐색을 하여 Maximum Flow가 현재 Limit을 걸고 Flow를 흘렸을 때와 동일한 지에 대해 판단합니다.

다르면 Limit이 적었다는 의미이므로 Limit을 늘려주고,

같다면 Limit이 충분하다는 의미이므로 Limit을 줄여주시면 됩니다.