[softeer] 루돌프 월드컵

01 May 2023 in Algorithm on Algorithm

https://softeer.ai/app/assessment/index.html?xid=462679&xsrfToken=lwAMIKqg6CwlidcTZlqpHIyEApV1JDJL&testType=practice

import java.util.*;

public class Main {
    static double totalProbability = 0.0;
    static double successfulProbability = 0.0;
    static int[] power = new int[4];
    static int[][] matches = {
            {0, 1},
            {0, 2},
            {0, 3},
            {1, 2},
            {1, 3},
            {2, 3}
    };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 4; i++) {
            power[i] = sc.nextInt();
        }
        dfs(0, new int[4], 1.0);
        System.out.printf("%.3f\n", successfulProbability * 100);
    }

    static void dfs(int matchIndex, int[] scores, double prob) {
        if (matchIndex == 6) {
            totalProbability += prob;
            if (isTopTwo(scores)) {
                successfulProbability += prob;
            }
            return;
        }

        int a = matches[matchIndex][0];
        int b = matches[matchIndex][1];
        double total = 5.0 * (power[a] + power[b]);
        double winA = 4.0 * power[a] / total;
        double winB = 4.0 * power[b] / total;
        double draw = 1.0 / 5.0;

        // A wins
        scores[a] += 3;
        dfs(matchIndex + 1, scores, prob * winA);
        scores[a] -= 3;

        // B wins
        scores[b] += 3;
        dfs(matchIndex + 1, scores, prob * winB);
        scores[b] -= 3;

        // Draw
        scores[a] += 1;
        scores[b] += 1;
        dfs(matchIndex + 1, scores, prob * draw);
        scores[a] -= 1;
        scores[b] -= 1;
    }

    static boolean isTopTwo(int[] scores) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            list.add(scores[i]);
        }
        list.sort(Collections.reverseOrder());
        int first = list.get(0);
        int second = list.get(1);
        int count = 0;
        if (scores[0] == first || scores[0] == second) {
            count++;
        }
        return count > 0;
    }
}