[Java] SWEA 1865번 : 동철이의 일 분배*

1. 문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc 

SW Expert Academy

 

 

 

2. 풀이과정

순서에 대한 순열에서 1)중간에 결과보다 작은 값이되거나  2)비트마스킹으로 불필요한 연산을 가지치기하는 것이 핵심이다.

 

예를 들어 N = 5일 때, 1~3까지 0~2번째 중에 하나씩 선택했다고 하면, 뒤에는 나머지는 3, 4번째 중에 선택한다.

이때 1~3까지 012, 021, 102, 120, 201, 210 순서가 가능한데, 이들 모두가 남은 것들의 최적값은 같다. 남아 있는 사용 가능한 순서값이 3, 4로 같기 때문이다.

 

따라서 0, 1, 2 세 개 선택한 것을 비트마스킹으로 해서 배열의 index값으로 사용하고 그 배열에 선택한 집합에 대한 최적 값을 저장했다.

 

import java.util.*;
import java.io.*;
 
class Solution
{
    static int N;
    static double map[][], dp[], result;
    public static void permutation(int cnt, int visited, double temp) {
        if(temp <= dp[visited] || temp<=result) {
            return;
        }
        dp[visited]=temp;
        if(cnt==N) {
            result = Math.max(result, temp);
            return;
        }
        for(int i=0; i<N; i++) {
            if((visited & (1<<i))!=0) {//이미 방문
                continue;
            }
            if(map[cnt][i]==0) {continue;}
            permutation(cnt+1, visited|(1<<i), temp*map[cnt][i]);
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
         
        int T = Integer.parseInt(br.readLine());
        for(int t=1; t<=T; t++) {
            sb.append("#").append(t);
            N = Integer.parseInt(br.readLine());
            result = 0;
            dp = new double[(1<<N)];
            dp[0] = -1;
            map = new double[N][N];
            for(int i=0; i<N; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<N; j++) {
                    map[i][j] = Double.parseDouble(st.nextToken())/100.0;
                }
            }
            permutation(0, 0, 1);
            sb.append(" ").append(String.format("%.6f", result*100)).append("\n");
        }
        System.out.println(sb.toString());
    }
}