문제풀이/백준
[백준]2341: DDR - JAVA
빈둥벤둥
2021. 2. 18. 13:34
[백준]2341: DDR

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 == 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;
}
}
|
cs |