SWEA_D4_1865

📁 [D4_1865] 동철이의 일 분배

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


public class Solution {
	static int N;
	static double max;
	static double[][] arr;
	static boolean[] v;

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

		// 테스트 케이스
		int tc = Integer.parseInt(br.readLine());

		for (int t = 1; t <= tc; t++) {
			sb.append("#").append(t).append(" ");

			// N
			N = Integer.parseInt(br.readLine());

			// 담당 배열
			arr = new double[N][N];

			// 방문 체크
			v = new boolean[N];

			// 확률 입력
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					arr[i][j] = Double.parseDouble(st.nextToken());
					arr[i][j] /= 100;
				}
			}

			max = 0;

			run(0,1.0);
			String str = String.format("%.6f", max*100);
			sb.append(str).append("\n");
		}
		System.out.println(sb);
	}

	static void run(int lev, double sum) {
		// 가지치기 ( 시간복잡도를 줄이는데 제일 중요 )
		if(sum <= max) return;
		// 기저조건
		if (lev == N) {
			max = Math.max(max, sum);
			return;
		}

		for(int i=0; i<N; i++) {
			// 이미 방문했으면 통과
			if(v[i]) continue;

			// 방문 처리
			v[i] = true;

			// 재귀
			run(lev+1, sum * arr[lev][i]);

			// 백트래킹
			v[i] = false;
		}
	}
}

🤔 나의 생각

재귀를 통해 문제를 해결했다.
같은 열은 사용할 수 없기 때문에 boolean 배열을 통해 열 요소의 방문처리를 해주었고
완탐형식으로 체크를 해준다.
그러나 여기서 중요한 것은 가지치기이다.
가지치기를 안해준다면 시간초과가 난다.
시간 복잡도를 줄이기에 가장 중요한 코드는 if(sum <= max) return; 이다.
이 코드를 통해 굳이 맨 밑에 행까지 갈 필요가 없는 것을 가지치기 해주면서 시간 복잡도를 확 줄여준다.
그리고 마지막으로 소수 6자리까지 출력해야하기 때문에 String.format을 통해 설정을 해준다.