소프트웨어 아카데미 1865 동철이의 일 분배 [자바]

02 Jun 2022 in Develop / Solving

SWEA

java

문제 분석

• N명의 직원, N개의 해야할 일
• i번 직원이, j번 일을 성공할 확률이 P_(i, j)로 나타남.
• 한 사람이 하나의 일을 할 때, 주어진 일이 모두 성공하는 최댓값

입력조건

테스트케이스 수 T
각 테스트 케이스마다 {
	사람 수 N
	N*N 개의 수
}

풀이과정

• 순열 사용
• 1번부터 할 일을 하나씩 지정해 주면서, 바로바로 확률을 계산하여 최대 확률보다 낮아지면 리턴하도록 백트래킹 진행.

코드 구성

• Stream으로 입력받기

  map[i] = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
  

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.Stream;

public class SWEA1865_동철이의일분배 {
	static int[][] map;
	static boolean[] clear;
	static double maxper;
	static int N;
	
	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 t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][];
			clear = new boolean[N];
			maxper = 0;
			
			for(int i = 0; i < N; i++)
				map[i] = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			// 입력받기 끝.
			
			select(0, 100);
			sb.append("#" + t + " " + String.format("%8.6f",maxper) + "\n");
		}
		System.out.println(sb);
	}
	public static void select(int sel, double per) {
		// 백트래킹
		if(Double.compare(maxper, per) >= 0) return;
		if(sel == N) {
			maxper = Math.max(maxper, per);
			return;
		}
		// 순열
		for(int i = 0; i < N; i++) {
			if(clear[i]) continue;
			clear[i] = true;
			
			select(sel+1, (per * (map[sel][i] / 100.0)));
			
			clear[i] = false;
		}
	}
}