[Java] 뮤탈리스크

https://www.acmicpc.net/problem/12869

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Arrays;

public class solution12869 {

	static ArrayList<int[]> permutationResult = new ArrayList<>();
	static int[][][] dp = new int[261][261][261];
	public static void main(String[] args) throws IOException {
		// Bufered Reader
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());

		int[] scvHealth = new int[3];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			scvHealth[i] = Integer.parseInt(st.nextToken()) + 200;
		}

		int[] orig = new int[] {9, 3, 1};
		int[] result = new int[N];
		boolean[] flag = new boolean[N];
		makePermutation(orig, result, 0, N, flag);
		
		System.out.println(findAnswerRecursive(scvHealth, N, 0));
	}
	
	public static void makePermutation(int[] orig, int[] result, int depth, int N, boolean[] flag) {
		if (depth == N) {
			permutationResult.add(Arrays.copyOf(result, result.length));
			return;
		}
		for (int i = 0; i < N; i++) {
			if (flag[i]) {
				continue;
			}
			flag[i] = true;
			result[depth] = orig[i];
			makePermutation(orig, result, depth + 1, N, flag);
			flag[i] = false;
		}
	}

	public static int findAnswerRecursive(int[] scvHealth, int N, int cnt) {
		
		if (dp[scvHealth[0]][scvHealth[1]][scvHealth[2]] != 0) {
			return dp[scvHealth[0]][scvHealth[1]][scvHealth[2]];
		}
	
		boolean isAllDead = true;	
		for (int i = 0; i < N; i++) {
			if (scvHealth[i] > 200) {
				isAllDead = false;
				break;
			}
		}
		
		if (isAllDead) {
			return cnt;
		}
		
		int minCnt = Integer.MAX_VALUE;
		for (int[] arr : permutationResult) {
			int[] damagedScvHealth = new int[3];
			for (int i = 0; i < N; i++) {
				damagedScvHealth[i] = scvHealth[i] - arr[i];
				if (damagedScvHealth[i] < 0) {
					damagedScvHealth[i] = 0;
				}
			}
			int res = findAnswerRecursive(damagedScvHealth, N, cnt + 1);
			minCnt = Math.min(minCnt, res);
		}
		dp[scvHealth[0]][scvHealth[1]][scvHealth[2]] = minCnt;
		return minCnt;
	} 
}

나의 풀이

- dfs + dp를 활용한 문제

- scv의 개수가 3개 이하로 가변적이어서 그에 따라 dp 배열을 유동적으로 맞춰주면 힘들어지겠지만 최대인 3개로 맞춰놓고 없는애는 그냥 0으로 처리해버리면 쉬워진다. 하지만 성능은 불리할 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {

	static ArrayList<int[]> permutationResult = new ArrayList<>();
	static int[][][] dp = new int[61][61][61];
	public static void main(String[] args) throws IOException {
		// Bufered Reader
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());

		int[] scvHealth = new int[3];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			scvHealth[i] = Integer.parseInt(st.nextToken());
		}

		int[] orig = new int[] {9, 3, 1};
		int[] result = new int[N];
		boolean[] flag = new boolean[N];
		makePermutation(orig, result, 0, N, flag);
		
		System.out.println(findAnswerRecursive(scvHealth, N));
	}
	
	public static void makePermutation(int[] orig, int[] result, int depth, int N, boolean[] flag) {
		if (depth == N) {
			permutationResult.add(Arrays.copyOf(result, result.length));
			return;
		}
		for (int i = 0; i < N; i++) {
			if (flag[i]) {
				continue;
			}
			flag[i] = true;
			result[depth] = orig[i];
			makePermutation(orig, result, depth + 1, N, flag);
			flag[i] = false;
		}
	}

	public static int findAnswerRecursive(int[] scvHealth, int N) {
		
		if (dp[scvHealth[0]][scvHealth[1]][scvHealth[2]] != 0) {
			return dp[scvHealth[0]][scvHealth[1]][scvHealth[2]];
		}

		boolean isAllDead = true;	
		for (int i = 0; i < N; i++) {
			if (scvHealth[i] > 0) {
				isAllDead = false;
				break;
			}
		}
		
		if (isAllDead) {
			return 0;
		}
		
		int minCnt = Integer.MAX_VALUE;
		for (int[] arr : permutationResult) {
			int[] damagedScvHealth = new int[3];
			for (int i = 0; i < N; i++) {
				damagedScvHealth[i] = scvHealth[i] - arr[i];
				if (damagedScvHealth[i] < 0) {
					damagedScvHealth[i] = 0;
				}
			}
			int res = findAnswerRecursive(damagedScvHealth, N) + 1;
			minCnt = Math.min(minCnt, res);
		}
		dp[scvHealth[0]][scvHealth[1]][scvHealth[2]] = minCnt;
		return minCnt;
	} 
}

나의 풀이

- 제일 위의 첫번째 풀이는 백준에서는 운이 좋게 맞긴 했는데 결과적으로 틀렸다. 각 dp가 나타내는게 현재 상태에서의 최소 개수를 의미해야하는데 그렇게 안된다. 왜냐하면 dp[0][0][0] = 0이어야 하는데 cnt로 되기 때문이다. 또한 서로 다른 경로에서 가면 결괏값이 달라질 수도 있다. 예를 들어, 간단하게 dp[3][3][3] -> dp[2][2][2] -> dp[1][1][1] -> dp[0][0][0] 이런 경로에서는 dp[1][1][1] = 3이 되겠지만 dp[2][2][2] -> dp[1][1][1] -> dp[0][0][0]에서는 dp[1][1][1] = 2가 되고 얘가 최소가 되어야 한다. 하지만 앞에걸 먼저하게 되면 dp[1][1][1] = 3으로 처리가 되어버린다. 아마 나의 첫번째 풀이에서는 200만큼 더해줘서 음수가 되어서 0으로 처리되는 상황이 애초에 없어서 중복이 없었기 때문으로 생각된다. 따라서 이를 고쳐서 위의 풀이는 dp가 현재 상태에서의 최소 개수를 나타내도록 수정을 하였다.