[백준 2342] - DDR(JAVA)[골드3]

문제

https://www.acmicpc.net/problem/2342

2342번: Dance Dance Revolution

문제 풀이

DP 문제로 판단하는 과정은 어렵진 않지만, 어떤 방법으로 풀어야 할지는 아직도 어려운 것 같다.

Top-down으로 풀지, Bottom-up으로 풀지, 재귀를 호출할지 등등..

나는 개인적으로 Bottom-up을선호한다.

해당 문제가 DP인 이유는 

이전 선택지에 현재 선택지가 영향을 받기 때문이다.

 

대부분 나는 이런 문제라고 판단이 되면 DP라고 못을 박는다.

예를 들어 1->2->2->4라면

2번에 대한 결과는 1번에서의 결과에 영향을 받는다.

즉 각 선택지는 이전 선택지에서의 결과에 영향을 받는다.

그래서 DP 배열을 통해서 선택지에 대한 결과를 저장한다.

 

내가 생각한 DP 배열은 다음과 같다.

• 3차원 배열이다. DP [i][j][k];
  • i는 왼발의 위치이다.
  • j는 오른발의 위치이다
  • k는 몇 번째 지시 사항까지 실행했는지를 뜻하는 idx값이다.

즉 DP [i][j][k]는 k번째 지시 사항에서 왼쪽발은 i, 오른쪽 발은 j인 비용의 최솟값이다.

2차원으로 풀고 싶었지만, 발의 종류와 지시 사항 idx가 반드시 필요했기 때문에 3차원으로 결정했다.

 

핵심인 DP 로직은 다음과 같다.

for (int idx = 1; idx < size; idx++) {
        int op = ary.get(idx); // 옮길 발의 위치.
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                dp[i][op][idx] = Math.min(dp[i][op][idx], dp[i][j][idx - 1] + moveCost(j, op));
                dp[op][j][idx] = Math.min(dp[op][j][idx], dp[i][j][idx - 1] + moveCost(i, op));
            }
        }
}

 

idx는 입력받은 지시사항의 index를 의미하고, i와 j는 각각 왼발과 오른발의 위치를 뜻한다.

우리는 왼발, 오른발 모두 움직이는 모든 경우의 수를 계산해야 한다.

op는 나아갈 발판의 위치를 의미한다.

그렇기 때문에 왼발 -> op, 오른발 -> op의 경우를 구해야 하고, 위 코드가 그 식이다.

moveCost(o1, o2)는 o1->o2로 갈 때의 비용을 구하는 함수이다.

 

dp [i][op][[idx]는 (i, j) -> (i, op)로 이동할 때의 최소비용이다.

그렇기 때문에 i, j, idx-1의 비용과 나아가기 위해 소요되는 비용을 더한 값과, 현재 값의 최솟값을 넣어준다.

반대편 발도 똑같은 원리로 계산을 해준다.

 

발판의 위치에 따라 비용을 계산하는 함수는 다음과 같다.

public static int moveCost(int pastOp, int nowOp) {
    if (pastOp == 0) { // 0에서 뻗어나가면 비용은 2
        return 2;
    } else if (pastOp == nowOp) { //발판이 같다면 비용은 1
        return 1;
    } else if ((pastOp + nowOp) % 2 == 0) { // 반대방향은 비용이 4
        return 4;
    } else { // 인접방향은 비용이3
        return 3;
    }
}

 

전체 코드

package eclipse_workspace;

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

public class Main {

	static BufferedReader br;
	static StringTokenizer st;
	static int max_value = 100000 * 4;
	static int[][] dir = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
	static ArrayList<Integer> ary;
	static int answer = max_value;
	static int[][][] dp;
	static int size;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		ary = new ArrayList<Integer>();
		ary.add(-1);
		input();
		run();
		System.out.print(answer);
	}

	public static void input() throws IOException {
		st = new StringTokenizer(br.readLine());
		int op = 0;
		while (st.hasMoreTokens()) {
			op = Integer.parseInt(st.nextToken());
			if (op == 0)
				break;
			ary.add(op);
		}
		size = ary.size();
		dp = new int[5][5][size]; // dp 배열 : 왼쪽발, 오른쪽발, 입력받은 명령의 수
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				for (int k = 0; k < size; k++) {
					dp[i][j][k] = max_value;
				}
			}
		}
	}

	public static void run() {
		dp[0][0][0] = 0;
		for (int idx = 1; idx < size; idx++) {
			int op = ary.get(idx); // 옮길 발의 위치.
			for (int i = 0; i < 5; i++) {
				for (int j = 0; j < 5; j++) {
					dp[i][op][idx] = Math.min(dp[i][op][idx], dp[i][j][idx - 1] + moveCost(j, op));
					dp[op][j][idx] = Math.min(dp[op][j][idx], dp[i][j][idx - 1] + moveCost(i, op));
				}
			}
		}
		int op = ary.get(size-1);
		for (int i = 0; i < 5; i++) {
			answer = Math.min(answer, dp[op][i][size - 1]);
			answer = Math.min(answer, dp[i][op][size- 1]);
		}
	}

	public static int moveCost(int pastOp, int nowOp) {
		if (pastOp == 0) { // 0에서 뻗어나가면 비용은 2
			return 2;
		} else if (pastOp == nowOp) { //발판이 같다면 비용은 1
			return 1;
		} else if ((pastOp + nowOp) % 2 == 0) { // 반대방향은 비용이 4
			return 4;
		} else { // 인접방향은 비용이3
			return 3;
		}
	}
}