[SWExpertAcademy] 1865. 동철이의 일 분배

문제

풀이

순열 문제
모든 케이스들의 확률비교
단, 현재 구한 최대 확률보다 낮으면 탐색할 필요가 없으므로 탐색 종료

코드

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;
			}
		}
	}
}