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

 

2342번: Dance Dance Revolution

입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마

www.acmicpc.net

코드설명

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;
}
}

+ Recent posts