sw expert academy 1865 동철이의 일 분배 자바(java) 풀이
문제정리
- N명의 직원, N개의 일 ( 한 사람당 하나의 일을 맡아서 진행 )
- 인덱스 : 1~N
- 주어진 일을 모두 성공할 확률의 최댓값 구하기
문제풀이
처음에는 그리디로 풀어볼까? 하는 생각이 들었다. 하지만 행에서 가장 큰 수만을 뽑아나간다 해도 최적의 해를 구할 수 없다.
최대 16개의 순열을 구해야한다.(1<=N<=16) 그렇기 때문에 이는 1초가 넘게 걸린다.
순열을 구할때 12,13개가 넘으면 이것은 바로 구하면 시간초과가 나겠구나 하고 생각해야한다.
왜냐하면 이 이상이 되면 기하급수적으로 계산해야할 양이 많아지기 때문이다.
어떻게 최적화 를 해서 구할지에 대한 고민을 해야한다.
조합을 이용하기
- 모든 경우를 계산한다. 가능한 조합을 재귀로 해서 구한다.
- 이때 cols[row]를 이용하여 각 row에서 선택한 col을 저장해두고 서로 다른 일을 할 수 있도록 한다.
- 하지만 그대로 모든 경우를 구한다면 시간초과가 뜬다.
- 그러므로 가지치기를 한다.
- 곱하는 값은 1보다 작은 소수이므로 곱하면 곱할수록 작아진다. 그러므로 곱해서 커지지 않는다면 계산을 하지 않는다.
- 그리고 곱해서 0이 나오는 경우 더 커질 수가 없다. 그러므로 이 경우도 가지로 쳐내준다.
순열을 이용하기
이 문제는 전형적인 TSP(여행자 문제)라고 볼 수 있다.
조합대신 순열을 이용해 모든 경우를 따져서 구할 수 있다.
행에서 어떤 열을 구하냐가 중요하기 때문에 순열로 구할 수 있다.
예를들어 3명이 있다면 순열을 통해 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)로 구할 수 있다.
열의 index를 구하면 된다는 것을 알 수 있다.
- int perm[16] = {0,1,2,...15} 까지 배열을 만든다
- 순열을 구하여 배열을 순회하며 값을 구해나가며 최대 값을 구한다.
for(int i=0; i<n; i++){
val *= mat[i][perm[i]];
}
중복된 계산 줄이기
이 내용은 코드에 넣지 않아도 통과는 된다.
값을 계산하다 보면은 중복된 계산들이 많다. 그러기 때문에 줄이면 좋다.
순열이 1234고 다음이 1243이라면 1,1행 값과 2,2행값을 곱한 값은 중복된 계산이 된다.
만약에 순열이 10개가 된다면 앞에 중복된 계산은 더욱 많게된다.
그렇기 때문에 그때까지 계산한 값을 파라미터로 넘겨서 그떄 변한 값만 계산하면 된다.
그리디를 이용하기
위에서 이야기했듯이 그리디로 풀면 정답이 나오지 않는다.
하지만 최적의 해를 구해나가기 때문에 정답은 아니지만 정답에 가까운 값이 나온다. 즉 정말 이상한 값이 나오지는 않는다.
그래서 정답 같은 그럴싸한 답부터 계산을 시작하면 좀더 빨리 답을 찾아낼 수 있다.
1865 동철이의 일 분배 자바 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
class Solution {
static double[][] arr;
static int n;
static double max;
static int[] cols;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int testNum = Integer.parseInt(br.readLine());
for(int test=1; test<=testNum; test++){
// init for test case
n = Integer.parseInt(br.readLine());
arr = new double[n+1][n+1];
cols = new int[n+1];
max = 0.0;
// 입력받기
// arr[j][k] = j번 사람이 k번째 일을 성공할 확률 (%)
for(int j=1; j<=n; j++){
// j: N개의 testcase
String[] temp = br.readLine().split(" ");
// k : N개의 수
for(int k=1; k<=n; k++){
arr[j][k] = Double.parseDouble(temp[k-1]) / 100.0;
}
}
comb(1, 1.0);
max *= 100;
bw.write("#" + test + " " + String.format("%.6f", max));
bw.newLine();
}
bw.flush();
bw.close();
br.close();
}
public static void comb(int row, double percent){
if(row == n+1){
max = max < percent ? percent : max;
return;
}
// col배열이 0으로 초기화해서 col 인덱스를 1~N까지
for(int col=1; col<=n; col++){
if(isValid(col)){
if(percent * arr[row][col] == 0)
continue;
if(percent * arr[row][col] < max)
continue;
cols[row] = col;
comb(row+1, percent* arr[row][col]);
cols[row] = 0;
}
}
}
public static boolean isValid(int y){
for(int i=1; i<=n; i++){
if(cols[i] == y)
return false;
}
return true;
}
}