순열 문제
모든 케이스들의 확률비교
단, 현재 구한 최대 확률보다 낮으면 탐색할 필요가 없으므로 탐색 종료
import java.io.*;
import java.util.*;
public class SWEA1865_동철이의_일_분배 {
static int N,arr[][];
static double answer;
static boolean[]visited;
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T=Integer.parseInt(br.readLine());
for(int tc=1;tc<=T;tc++) {
//tc 입력 시작
N=Integer.parseInt(br.readLine());
arr=new int[N][N];
visited=new boolean[N];
answer=0;
for(int i=0;i<N;i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
arr[i][j]=Integer.parseInt(st.nextToken());
}
}
//tc 입력end
dfs(0,100);
bw.write("#"+tc+" "+String.format("%.6f", answer)+"\n");
}
bw.flush();
}
static void dfs(int depth,double nowP) {
//현재 최대 확률보다 낮으면 탐색 종료
if(answer>=nowP)return;
//N명에게 N개의 업무를 모두 배정한 경우 최댓값으로 확률 갱신
if(depth==N){
answer=Math.max(answer, nowP);
return;
}
for(int i=0;i<N;i++) {
if(!visited[i]){
visited[i]=true;
dfs(depth+1, nowP*arr[depth][i]*0.01);
visited[i]=false;
}
}
}
}