SW Expert Academy - 1865(동철이의 일 분배)

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static double res;

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(reader.readLine());    // 테스트케이스

        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(reader.readLine());    // 직원, 일의 수

            int[][] percent = new int[N][N];
            StringTokenizer tokenizer = null;
            for (int i = 0; i < N; i++) {
                tokenizer = new StringTokenizer(reader.readLine());
                for (int j = 0; j < N; j++) {
                    percent[i][j] = Integer.parseInt(tokenizer.nextToken());
                }
            }

            res = 0;

            permutation(percent, new boolean[N], 1, N, 0);

            sb.append("#").append(t + 1).append(" ");
            sb.append(String.format("%.6f", res * 100)).append("\n");
        }

        System.out.println(sb);
    }

    private static void permutation(int[][] percent, boolean[] isVisited, double curr, int N, int cnt) {
        if (cnt == N) {
            res = Math.max(res, curr);
            return;
        }

        if (curr <= res) {
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!isVisited[i]) {
                double temp = curr;
                isVisited[i] = true;
                curr *= percent[cnt][i] * 0.01;
                permutation(percent, isVisited, curr, N, cnt + 1);
                isVisited[i] = false;
                curr = temp;
            }
        }
    }

}

• 자괴감이 든다... 처음에 댓글에 DP, DFS와 같은 알고리즘이 언급되어서 이를 활용해보려 애쓰다가 생각이 안나 구글링을 했다.
• 순열과 백트래킹을 이용해서 푸는 풀이가 많았는데, 순열을 처음에 생각하긴 했으나 수가 커서 포기했던 방법이었다.
• 일단 시도해 보는 부분이 필요한 것 같다.