[SWEA] 동철이의 일 분배

Posted on | In |

문제 보러가기

제한사항

모든 일을 성공할 확률이 최대화될 때의 확률을 퍼센트 단위로 소수점 아래 7번째 자리에서 반올림하여 6번째까지 출력한다.

첫번째 생각

일에 대한 확률을 0.01%로 계산해야하므로 process 배열에 넣을때 /100을 해서 넣어준 뒤,

dfs로 탐색하여 최댓값을 구한다.

JAVA Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.Scanner;

public class Solution {
	static int N;
	static double[][] process;
	static int[] job;
	static double max;
	static boolean[] visit;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			process = new double[N][N];
			job = new int[N];
			visit = new boolean[N];
			max = 0.0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					process[i][j] = sc.nextInt() / 100.0;
				}
			}
			dfs(0, 1.0);
			System.out.printf("#%d %.6f", tc, max);
			System.out.println();
		}
	}

	public static void dfs(int depth, double sum) {
		if (sum * 100 <= max)
			return;
		if (depth == N) {
			if (sum * 100 > max) {
				max = sum * 100;
				return;
			}
		}

		for (int i = 0; i < N; i++) {
			if (!visit[i]) {
				visit[i] = true;
				dfs(depth + 1, sum * process[depth][i]);
				visit[i] = false;
			}
		}
	}
}