백준 2342 Dance Dance Revolution 자바

🔗 백준 2342 Dance Dance Revolution 

📌오늘의 학습 키워드

• DP 문제

✨공부한 내용 본인의 언어로 정리하기

• 3차원 배열에 DP를 저장해야했다.
• 전체적인 논리는 각 단계의 이전까지의 정보를 가지고 현재 값을 업데이트하여 계속 총 비용을 계산해 나가는 것이다.

 

📚오늘의 회고

• DP에서 무엇을 저장하고 어떻게 작은 문제로 나눌 것인 지 생각하는 게 쉽지 않다...

[🤓문제 해결 코드]

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

public class Main {
	static int[] arr;
	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];
		
		int num, idx=0;
		while(true) {
			num = Integer.parseInt(st.nextToken());
			if(num == 0)
				break;
			arr[++idx] = num;
		}
		
		dp = new int[2][5][5];
		
		// 0 이전, 1 현재
		for(int i=0; i<5; i++) {
			for(int j=0; j<5; j++) {
				dp[0][i][j] = Integer.MAX_VALUE;
				dp[1][i][j] = Integer.MAX_VALUE;
			}
		}
		
		dp[0][0][0] = 0;
		int next = 0;
		
		// 들어온 숫자를 순회
		for(int k=1; k<=idx; k++) {
			next = arr[k];
			for(int i=0; i<5; i++) {
				for(int j=0; j<5; j++) {
					// 불가능한 상황이면 패스
					if(dp[0][i][j] == Integer.MAX_VALUE)
						continue;
					
					dp[1][i][next] = Math.min(dp[1][i][next], dp[0][i][j] + cost(j, next));
					dp[1][next][j] = Math.min(dp[1][next][j], dp[0][i][j] + cost(i, next));
				}
			}
			
			// 값 복사하고 현재값 초기화
			for(int i=0; i<5; i++) {
				for(int j=0; j<5; j++) {
					dp[0][i][j] = dp[1][i][j];
					dp[1][i][j] = Integer.MAX_VALUE;
				}
			}
			
			for(int i=0; i<5; i++) {
				for(int j=0; j<5; j++) {
					System.out.printf("%d ", dp[0][i][j]);
				}
				System.out.println();
			}
			System.out.println();
		}
		
		// 마지막까지 왔을 때의 최적값들만 업데이트 되어있음
		int ans = Integer.MAX_VALUE;
		for(int i=0; i<5; i++) {
			ans = Math.min(ans, dp[0][i][next]);
			ans = Math.min(ans, dp[0][next][i]);
		}
		
		System.out.println(ans);
	}
	
	static int cost(int a, int b) {
		if(a == b)
			return 1;
		
		if(a == 0 || b == 0) {
			return 2;
		}
		
		if(Math.abs(a-b)==2) {
			return 4;
		}
		
		return 3;
	}
}