[백준] 2342 Dance Dance Revolution - 탑다운DP

문제 링크 : https://www.acmicpc.net/problem/2342

🍊해결방법

• 왼발, 오른발 방향의 값에 따라 결과값이 달라짐
• 왼발로 이동하는 경우의 수와 오른발로 이동하는 경우의 수 확인
• dirCal() 함수를 통해 방향에 이동에 대한 값 계산
• 왼발이동하는 값(tmp1) 과 오른발이동하는 값(tmp2) 최솟값 return
• 중복되는 경우 있으므로 dp 활용해서 저장

😀풀이

import java.util.*;
import java.io.*;

public class Main {

    static int N;
    static int[] arr;
    static int[][][] dp;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 왼발 오른발에 방향 저장
        // 문제의 조건에 맞게 방향 이동할때 힘 적용
        // 마지막까지 했을 때 최솟값 갱신
        // 중복되는 상황이 있을 수 있으므로 dp 사용

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = st.countTokens()-1;

        arr = new int[N];

        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp = new int[N][5][5];

        for(int i=0; i<N; i++){
            for(int j=0; j<5; j++){
                Arrays.fill(dp[i][j], -1);
            }
        }


        int ans = go(0,0,0);


        System.out.println(ans);

    }

    static int go(int idx, int left, int right){

        if (idx == N){
            return 0;
        }

        if (dp[idx][left][right] != -1) return dp[idx][left][right];

        int power = dirCal(arr[idx], left);
        int tmp1 = go(idx+1, arr[idx], right) + power;

        power = dirCal(arr[idx], right);
        int tmp2 = go(idx+1, left, arr[idx]) + power;

        int tmp = Math.min(tmp1, tmp2);

        dp[idx][left][right] = tmp;


        return dp[idx][left][right];
    }

    static int dirCal(int next, int now){

        if (now == 0) return 2;

        if (now == next) return 1;

        if (now == 1 && next == 3 || now == 3 && next == 1) return 4;

        if (now == 2 && next == 4 || now == 4 && next == 2) return 4;

        return 3;
    }


}