[백준] 2342 Dance Dance Revolution - DP + 재귀 JAVA

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

2342번: Dance Dance Revolution

코드설명

Top-Down 방식의 DP 방식을 활용합니다.

 

재귀를 활용하여 움직임에 따라서 에너지를 계속해서 갱신해나갑니다.

이전에 계산했었던 위치와 level일경우 계산을 생략하여 시간초과를 피할 수 있습니다.

코드

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

public class Main {
	
	public static int N, M, K;
	public static int answer;
	public static int endIdx = 0;
	public static int[] arr;
	public static int[][][] dp;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	arr = new int[100001];
    	
    	for(int i=0; ;i++) {
    		int temp = Integer.parseInt(st.nextToken());
    		if(temp == 0) {
    			endIdx = i;
    			break;
    		}else {
    			arr[i] = temp;	
    		}
    	}
    	dp = new int[endIdx + 1][5][5];
    	
    	System.out.println(simulate(0, 0, 0));
	}
	
	public static int simulate(int level, int leftFoot, int rightFoot) {
		if(dp[level][leftFoot][rightFoot] > 0) return dp[level][leftFoot][rightFoot];
		if(endIdx == level) {
			return 0;
		}
		
		int temp1 = calculate(leftFoot, arr[level]) + simulate(level + 1, arr[level], rightFoot);
		int temp2 = calculate(rightFoot, arr[level]) + simulate(level + 1, leftFoot, arr[level]);
				
		return dp[level][leftFoot][rightFoot] = Math.min(temp1, temp2);
		
	}
	public static int calculate(int start, int end) {
		int distance = Math.abs(start - end);
		if(start == 0) return 2; //중간에서 시작한다면 무조건 2의 에너지가 듭니다.
		else if(distance == 0) return 1; //계속 같은 위치에 존재한다면,
		else if(distance == 1 || distance == 3) return 3;
		else return 4;
	}
		
}