[SWEA] 1865. 동철이의 일 분배

 출처 

1865. 동철이의 일분배

SW Expert Academy

 

코드

1. 정수 N의 범위가 1~16이므로 순열을 활용할 수 있다는 것을 파악했습니다. (제한시간이 자바는 30초로 넉넉한 연산시간)

2. 처음에는 순열의 경우의 수를 tmp배열에 담아서 caculate() 만들어서 함수 내에서 계산했으나 시간초과로 실패했습니다.

3. 그래서 다음으로 생각한 것이 계산 자체도 permutation()내에서 해버리는 것이었습니다.

4. 처음부터 arr에 넣어줄 입력을 받을 때 100.0으로 나누어서 값을 저장해 주었고, 이를 바탕으로 permutaion() 에서는 double tmp값에 arr값을 곱해주면서 다음 턴으로 넘어가는 재귀를 수행했습니다. 여기서 중요한 것은 permutation의 첫번째 if문에서 max보다 작은 tmp는 리턴하는 것입니다. 이 코드가 없을 시 max값 보다 작더라도 계속해서 의미없는 턴을 수행하기 때문에 재귀호출량이 더 많아져서 필요없는 호출은 없애 시간초과를 방지해야합니다.

import java.io.*;
import java.util.*;

class Solution {
    static double arr[][];
    static double max = 0.0;

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

        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());

            arr = new double[N][N];
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    arr[i][j] = Double.parseDouble(st.nextToken()) / 100.0;
                }
            }

            // 123 132 213 231 312 321 -> 순열
            boolean[] visit = new boolean[N];
            max = 0.0;
            permutation(0, N, 1, visit);

            sb.append("#" + tc + " " + String.format("%.6f", max * 100) + "\n");
        }
        System.out.println(sb);
    }

    public static void permutation(int cur, int N, double tmp, boolean[] visit) {
    	//max값 보다 작으면 리턴해서 끝내기
        if (tmp <= max) {
            return;
        }
        if (cur == N) {
            max = Math.max(max, tmp);
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true;
                permutation(cur + 1, N, tmp * arr[cur][i], visit);
                visit[i] = false;
            }
        }
    }
}