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; } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1103 게임 - DP + 깊이우선탐색(DFS, 재귀) JAVA (0) | 2023.11.16 |
---|---|
[백준] 11049 행렬 곱셈 순서 - DP + 재귀 + 수학 JAVA (0) | 2023.11.14 |
[백준] 16235 나무 재테크 - 시뮬레이션 + 우선순위큐(Priority Queue) + 자료구조 + 시간초과 JAVA (0) | 2023.11.13 |
[백준] 1525 퍼즐 - BFS(너비우선탐색) + HashMap + StringBuilder JAVA (0) | 2023.11.11 |
[백준] 2234 성곽- 비트마스킹(BitMasking) + BFS(너비우선탐색) JAVA (0) | 2023.11.11 |