1865. 동철이의 일 분배

문제 출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc&categoryId=AV5LuHfqDz8DFAXc&categoryType=CODE

동철이가 싼 똥처리 하느라 힘들었네요.

똥철아 너가 싼 똥은 너가 치워야지......

똥철아 그러지마.....

문제 들어가면 리플에 DFS로 시간 초과나니 DP로 해야할것 같다는 리플이 달려있습니다.

아주아주 큰 함정이네요.

DFS로 안풀고 다른 걸로 풀다가 답이 안나오길래

DFS에서 조건 하나 거니깐 답이 제대로 나옵니다.

(다시 보니 스캐너를 넘기는게 참 이상하네요. 걍 solution 메소드를 사용하지 마세요)

(5분 후 컴퓨터를 뜯어서 청소할 예정인데..... 문제없기를 바랄뿐입니다.)

import java.util.Scanner; public class Q1865 { static double realResult; static int size; static boolean[] isUsed; static double[][] table; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int testCase = sc.nextInt(); for (int i = 0; i < testCase; i++) { realResult = 0; solution(i+1, sc); } } static void solution(int num, Scanner sc) { size = sc.nextInt(); table = new double[size][size]; isUsed = new boolean[size]; for (int j = 0; j < size; j++) { for (int k = 0; k < size; k++) { table[j][k] = sc.nextDouble()/100; } } calResult(0, 100); System.out.printf("#%d %.6f\n",num, realResult); } static void calResult(int count, double result) { if (realResult < result){ if (count == size) { realResult = result; return; } for (int i = 0; i < size; i++) { if (isUsed[i]) { continue; } isUsed[i] = true; double tempResult = result * table[count][i]; calResult(count+1, tempResult); isUsed[i] = false; } } } }

2018년 3월 25일 import java.util.Scanner; public class Q1865 { static double result; static double[][] values; static boolean[] isUsed; static int N; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int testCase = sc.nextInt(); for (int i = 1; i <= testCase; i++) { result = 0; N = sc.nextInt(); isUsed = new boolean[N]; values = new double[N][N]; for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { values[j][k] = sc.nextDouble()/100; } } calResult(0, 100); System.out.printf("#%d %.6f\n", i, result); } } static void calResult(int count, double nowResult) { if (result >= nowResult) { return; } if (count == N) { result = nowResult; return; } for (int i = 0; i < N; i++) { if (isUsed[i]) { continue; } double tempResult = nowResult; tempResult *= values[count][i]; isUsed[i] = true; calResult(count+1, tempResult); isUsed[i] = false; } } }