문제풀이/백준

[백준]2341: DDR - JAVA

빈둥벤둥 2021. 2. 18. 13:34

[백준]2341: DDR

www.acmicpc.net/problem/2342

 

2342번: Dance Dance Revolution

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

www.acmicpc.net

 

풀이

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

 

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

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

1. 왼쪽 발을 옮기는 경우

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

 

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

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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 == 0break;
            nums.add(n);
        }
        
        dp = new int[nums.size()][5][5]; //현재 밟아야할 순서, 왼발의 위치, 오른발의 위치
        System.out.println(dfs(000));
    }
    
    public static int dfs(int idx, int left, int right) {
        if(idx == nums.size()) return 0;
        if(dp[idx][left][right] != 0return 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 == 0return 2;
        else if(Math.abs(start - end) == 2return 4;
        else if(start == end) return 1;
        else return 3;
    }
}
cs