백준 12869번: 뮤탈리스크

문제 설명

• https://www.acmicpc.net/problem/12869
• 뮤탈리스크는 한번의 공격으로 최대 3개의 SCV를 공격합니다.
  첫번째 공격으로 9, 두번째 공격으로 3, 세번째 공격으로 1의 체력을 깎습니다.
  SCV는 체력이 0이되면 즉시 없어지며 한 반의 공격으로 같은 SCV를 여러번 공격할 수 없습니다.

접근법

• dp배열을 어떻게 설계하는지가 가장 중요합니다.
  • 처음에는 세로축이 SCV, 가로축이 공격횟수, dp[i][j]가 남은 체력인 2차원 배열을 생각했으나 dp[j]와 dp[j+1] 사이의 관계를 파악하기 어려워 포기했습니다.
    
    • SCV체력이 높은 순서대로 9,3,1의 공격을 한다라는 규칙을 생각했지만 예제1은 해당 규칙으로 풀 수 없었습니다.
• N의 크기가 작아 완전탐색을 고려했습니다.
  • 공격으로 가능한 경우의 수는 6가지 입니다. {{9,3,1},{9,1,3},{3,9,1},{3,1,9},{1,9,3},{1,3,9}} 현재 위치에서 6가지 경우의 수를 계속 탐색해 {0,0,0}일 때 return하는 BFS를 구현해 봤습니다. -> 시간초과가 발생했습니다.
  • 시간초과를 해결하기 위해 방문정보를 담은 dp(memoization)배열을 만들어 문제를 해결했습니다.

처음부터 dp문제니깐 dp배열을 만들어야 한다는 생각보다 문제의 조건을 읽으면서 BFS를 1차적으로 생각하고, BFS의 시간을 줄이기 위해 dp개념을 활용하는 문제였습니다.
dp문제라기보다는 BFS 시간 최적화 문제에 가깝습니다.

정답

import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
	static int[][] possibleAttack = {{9,3,1},{9,1,3},{3,9,1},{3,1,9},{1,9,3},{1,3,9}};
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[3];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();;
		}
		int[][][] dp = new int[arr[0]+1][arr[1]+1][arr[2]+1];
		dp[arr[0]][arr[1]][arr[2]] = 0;
		BFS(new int[]{arr[0],arr[1],arr[2]}, dp);
		System.out.println(dp[0][0][0]);
		
	}
	
	public static void BFS(int[] start, int[][][] dp) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(start);
		while(!q.isEmpty()) {
				int[] now = q.poll();
				if(now[0] == 0 && now[1] == 0 && now[2] == 0) return ;
				for (int d = 0; d < 6; d++) {
					int[] attack = possibleAttack[d];
					int a = (now[0] - attack[0]>0)?now[0] - attack[0]:0;
					int b = (now[1] - attack[1]>0)?now[1] - attack[1]:0;
					int c = (now[2] - attack[2]>0)?now[2] - attack[2]:0;
					if(dp[a][b][c] ==0) {
						q.add(new int[] {a,b,c});
						dp[a][b][c] = dp[now[0]][now[1]][now[2]] +1;
					}
				}

		}
	}
}