<Algorithm> 133. 동철이의 일분배(SWExpert)

1. 동철이의 일분배(SWExpert)

• DFS 탐색 문제

• 처음에 모든 경우를 탐색했을때는 시간초과가 발생해서 max값이 될 수 없는 (곱하면 작아지는 확률) 것은 탐색하지 않으니 통과했다.

• 또 6자리 뒤에 0이 안붙으면 fail이 나서 소수점 여섯자리를 다 표시해 주어야 한다.

import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Stream;
 
public class Solution {
    
    public static boolean[] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        /******************************
         * DFS 탐색을 이용하여 선택하는 모든 경우를
         * 탐색한다. 이때 max 값이 될 수 없는 경우는
         * 탐색하지 않는다.
         *******************************/
        for(int t = 1; t <= T; t++) {
            int N = sc.nextInt();
            double[][] arr = new double[N][N];
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    arr[i][j] = sc.nextInt()*0.01;
                }
            }
            visited = new boolean[N];
            max = -1;
            req(0, N, arr, 1);
            max = max*100;
            System.out.println("#"+t+" "+String.format("%.6f", max));
            
        }
        
    }
    static double max;
    public static void req(int deep,int N, double[][] arr , double total) {
        
        if( total <= max ) return;
        
        if(deep == N) {
            max = Math.max(max, total);
            return;
        }
        
        for(int i = 0; i < N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                req(deep+1, N, arr, total*arr[deep][i]);
                visited[i] = false;
            }
        }
        
    }
}
 

참고 & 출처