[백준]2341: DDR - JAVA

[백준]2341: DDR

www.acmicpc.net/problem/2342

2342번: Dance Dance Revolution

 

풀이

DP문제로 왼쪽, 오른쪽 발의 위치를 바꾸어 가면서 최소값을 찾아내야 한다. 이때 항상 이전의 왼쪽 발의 위치와 오른쪽 발의 위치를 기억하고 있어야 해서 DP를 3차원 배열로 선언해 주었다.

 

DP[][][]에서 각 자리의 의미는 DP[현재 밟아야 할 위치][이전의 왼쪽발 위치][이전의 오른쪽발 위치]이다. 

이러한 상황에서 두 가지 경우가 존재한다. 

1. 왼쪽 발을 옮기는 경우

2. 오른쪽 발을 옮기는 경우

 

왼쪽, 오른쪽 둘다 발을 옮긴 후 둘 중에 이동 값이 최솟값인 결과를 선택하면 된다.

 

코드

import java.util.*;
 
public class Main {    
    
    static ArrayList<Integer> nums;
    static int[][][] dp;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        nums = new ArrayList<>();
        while(true) {
            int n = scan.nextInt();
            if(n == 0) break;
            nums.add(n);
        }
        
        dp = new int[nums.size()][5][5]; //현재 밟아야할 순서, 왼발의 위치, 오른발의 위치
        System.out.println(dfs(0, 0, 0));
    }
    
    public static int dfs(int idx, int left, int right) {
        if(idx == nums.size()) return 0;
        if(dp[idx][left][right] != 0) return dp[idx][left][right];
        
        int goLeft = dfs(idx + 1, nums.get(idx), right) + going(left, nums.get(idx));
        int goRight = dfs(idx + 1, left, nums.get(idx)) + going(right, nums.get(idx));
        dp[idx][left][right] = Math.min(goLeft, goRight);
        
        return dp[idx][left][right];
    }
    
    public static int going(int start, int end) {
        if(start == 0) return 2;
        else if(Math.abs(start - end) == 2) return 4;
        else if(start == end) return 1;
        else return 3;
    }
}