요원 미션 배정
시간 제한1초메모리 제한128 MB
N x N 확률 행렬이 주어질 때 각 요원에게 임무를 하나씩 배정해 성공 확률의 곱을 최대화하는 할당 문제를 풉니다.
문제
비밀 요원 007은 매달 여러 미션을 받고, 자신과 닮은 사촌 요원들에게 미션을 하나씩 맡긴다. 요원 수와 미션 수는 모두 N이다.
각 요원 i가 미션 j를 성공할 확률이 퍼센트로 주어진다. 한 요원은 정확히 하나의 미션만 맡고, 각 미션도 정확히 한 요원에게만 배정해야 한다.
모든 미션이 성공할 확률은 배정된 각 미션의 성공 확률을 모두 곱한 값이다. 이 값이 최대가 되도록 미션을 배정했을 때, 모든 미션이 성공할 최대 확률을 구하라.
입력
첫째 줄에 미션과 요원의 수 N이 주어진다. (1 <= N <= 20)
다음 N개 줄에는 0 이상 100 이하의 정수가 N개씩 주어진다. i번째 줄의 j번째 정수는 요원 i가 미션 j를 성공적으로 마칠 확률이며, 퍼센트 단위이다.
출력
모든 미션을 성공적으로 마칠 수 있는 최대 확률을 퍼센트로 출력한다. 정답과의 오차는 0.000001까지 허용된다.