문제

풀이

아이디어

BFS(실패 : 시간초과)

탐색 문제라고 생각하여 BFS로 문제를 풀어봤습니다.

탐색할 때 마다 큐에 현재 바라보고 있는 위치, 여태 사용한 에너지, 그리고 깊이를 저장했습니다.

그래서 현재 방향이 처음 위치와 같고 에너지를 전부 소모하였는지를 체크하였습니다.

	static int[] cost = new int[3];
	static int[] dir = {3, 1, 2};

다음과 같이 방향을 좌, 우, 뒤로 돌아를 표현하였고

		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] {0, K, 0});
		
		while(!queue.isEmpty()) {

큐에 0,K,0 으로 방향, 여태 쓴 에너지, 그리고 깊이를 저장하였습니다.

			int[] cur = queue.poll();
			if(cur[0]==0 && cur[1] == 0) {
				System.out.println(cur[2]);
				return;
			}
			for(int di=0; di<3; di++) {
				int ndir = (cur[0] + dir[di]) % 4;
				int nenergy = cur[1] - cost[di];
				
				if(nenergy < 0)
					continue;
				queue.add(new int[] {ndir, nenergy, cur[2] + 1});
			}

이제 큐를 돌면서 현재 값이 조건을 충족하면 출력하도록 하고 3방향으로 회전하도록 설계하였습니다.

이렇게 하였으나 결과는 시간 초과!

시간 초과가 발생하는 원인은 최소로 가는 깊이만 생각해야 합니다.
근데 깊이가 더 깊으면서 소모하는 에너지가 많은 경우를 생각해야 하기 때문입니다.

예를 들어서 좌로 도는데에 1이 소모되고 뒤로 도는데 2가 소모된다고 생각해봅시다.

좌 - 좌 - 좌 - 좌로 총 4의 에너지를 소모하고 원래 위치로 갑니다. 깊이는 4입니다.
뒤 - 뒤 총 4의 에너지를 소모하고 원래 위치로 갑니다. 깊이는 2입니다.

이 경우 똑같은 에너지를 소모했지만 깊이가 짧은 뒤-뒤 루트에서 더 계산을 해야 합니다. 그러나 위의 코드는 '좌-좌-좌-좌'의 루트를 계속 보게 됩니다.

이를 해결하기 위해 다른 아이디어가 필요합니다.

---

DP(성공)

dp를 통해 문제를 해결해봅시다.

2차원 배열로 int[에너지][방향]으로 거기 까지 도달하는 최소 깊이를 저장해줍니다.

dp [A][B] = A에너지를 소모해서 B방향을 볼때의 최소 깊이

우리는 이제 dp[K][0]을 구해주면 됩니다.

		dp = new int[K+1][4];
		
		for(int i=0; i<=K; i++) {
			Arrays.fill(dp[i], 1_000_001);
		}

다음과 같이 dp에 최댓값을 넣어 초기화합니다.

		dp[0][0] = 0;
		for(int i=0; i<=K; i++) {
			for(int j=0; j<4; j++) {
				if(dp[i][j] == 1000001)
					continue;
				for(int c=0; c<3; c++) {
					if(i+cost[c] > K)
						continue;
					dp[i + cost[c]][(j + dir[c]) % 4] = Math.min(dp[i + cost[c]][(j + dir[c]) % 4], dp[i][j] + 1); 
				}
			}
		}

다음과 같이 각 방향별로 cost값을 더해주고 그 값의 최소 깊이를 기록해줍니다.

이런 방식으로 dp[K][0]의 값을 구해줍니다.

dp[K][0] == 1_000_001일 경우 -1을 반환함으로서 문제를 해결할 수 있습니다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// dp로 문제 풀어보기
public class No27114_1 {
	static int K;
	static int[] cost = new int[3];
	static int[] dir = {3, 1, 2};
	static int[][] dp;
	public static void main(String[] args) throws IOException {
		input();
		pro();
	}
	private static void pro() {
		dp = new int[K+1][4];
		
		for(int i=0; i<=K; i++) {
			Arrays.fill(dp[i], 1_000_001);
		}
		
		dp[0][0] = 0;
		for(int i=0; i<=K; i++) {
			for(int j=0; j<4; j++) {
				if(dp[i][j] == 1000001)
					continue;
				for(int c=0; c<3; c++) {
					if(i+cost[c] > K)
						continue;
					dp[i + cost[c]][(j + dir[c]) % 4] = Math.min(dp[i + cost[c]][(j + dir[c]) % 4], dp[i][j] + 1); 
				}
			}
		}
		
		if(dp[K][0] == 1000001)
			dp[K][0] = -1;
		System.out.println(dp[K][0]);
	}
	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		cost[0] = Integer.parseInt(st.nextToken());
		cost[1] = Integer.parseInt(st.nextToken());
		cost[2] = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		br.close();
	}
}