[BOJ 백준] Dance Dance Revolution (2342) Java

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

 

문제 설명 : 

승환이는 요즘 "Dance Dance Revolution"이라는 게임에 빠져 살고 있다. 하지만 그의 춤 솜씨를 보면 알 수 있듯이, 그는 DDR을 잘 하지 못한다. 그럼에도 불구하고 그는 살을 뺄 수 있다는 일념으로 DDR을 즐긴다.

DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의 중점을 기준으로 위, 아래, 왼쪽, 오른쪽으로 연결되어 있다. 편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4라고 정하자.

처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오른쪽 발을 움직인다. 하지만 그의 두 발이 동시에 움직이지는 않는다.

이 게임에는 이상한 규칙이 더 있다. 두 발이 같은 지점에 있는 것이 허락되지 않는 것이다. (물론 게임 시작시에는 예외이다) 만약, 한 발이 1의 위치에 있고, 다른 한 발이 3의 위치에 있을 때, 3을 연속으로 눌러야 한다면, 3의 위치에 있는 발로 반복해야 눌러야 한다는 것이다.

오랫동안 DDR을 해 온 백승환은 발이 움직이는 위치에 따라서 드는 힘이 다르다는 것을 알게 되었다. 만약, 중앙에 있던 발이 다른 지점으로 움직일 때, 2의 힘을 사용하게 된다. 그리고 다른 지점에서 인접한 지점으로 움직일 때는 3의 힘을 사용하게 된다. (예를 들면 왼쪽에서 위나 아래로 이동할 때의 이야기이다.) 그리고 반대편으로 움직일때는 4의 힘을 사용하게 된다. (위쪽에서 아래쪽으로, 또는 오른쪽에서 왼쪽으로). 만약 같은 지점을 한번 더 누른다면, 그때는 1의 힘을 사용하게 된다.

만약 1 → 2 → 2 → 4를 눌러야 한다고 가정해 보자. 당신의 두 발은 처음에 (point 0, point 0)에 위치하여 있을 것이다. 그리고 (0, 0) → (0, 1) → (2, 1) → (2, 1) → (2, 4)로 이동하면, 당신은 8의 힘을 사용하게 된다. 다른 방법으로 발을 움직이려고 해도, 당신은 8의 힘보다 더 적게 힘을 사용해서 1 → 2 → 2 → 4를 누를 수는 없을 것이다.

 

입력 :

입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마지막을 의미한다. 즉, 입력 파일의 마지막에는 0이 입력된다. 입력되는 수열의 길이는 100,000을 넘지 않는다.

 

출력 : 

한 줄에 모든 지시 사항을 만족하는 데 사용되는 최소의 힘을 출력한다.

 

예제 입력 : 

1 2 2 4 0

 

예제 출력 : 

8

 

 

접근법 : 

1) 어떻게 풀 것인가?

왼쪽 발과 오른쪽 발의 움직임이 서로 영향을 준다.

카드 게임 https://subbak2.tistory.com/78 문제와 유사한 점이 많다.

 

이전의 행동이 지금 행동의 점수에 영향을 주기 때문에 DP로 다 해보기로 한다.

 

dp[ i ] [ j ] [ k ] 를 왼발(j) 위치, 오른발(k) 위치이고, i번째 스텝일때 최댓값 으로 정의하고

분할정복 형태로 풀었다.

 

static int DDR(int step, int left, int right) {
		// 1. 마지막 스텝 도달하면 끝
		if (step == N)
			return 0;

		// 2. dp에 값이 차있으면 return
		if (dp[step][left][right] != 0) {
			return dp[step][left][right];
		}

		// 3. 가능한 경우의 수 중 가장 적은 경우로 갱신하고 return
		// 왼발 욺직이는 경우 vs 오른발 움직이는 경우
		int leftScore = score(left, input.get(step)) + DDR(step + 1, input.get(step), right); 
		int rightScore = score(right, input.get(step)) + DDR(step + 1, left, input.get(step)); 
		
		return dp[step][left][right] = Math.min(leftScore, rightScore);
	}

 

점수를 구하는 코드는 절대값을 이용해 나눠봤다.

static int score(int from, int to){
    	// 0. 지금 위치를 누르면 1
    	if(from==to) return 1;
    	// 1. 가운데 출발 2
        if(from==0) return 2;
        // 3. 크로스 해서 밟으면 4
        if(Math.abs(from-to) ==2) return 4;
        // 4. 인접 스텝 밟으면 3
        return 3;
    }

 

전체 코드는 아래 참고.

 

2) 시간복잡도

최악의 경우 N^2 예상되나, DP 가지치기로 무리 없이 통과됨.

(Java 기준 - 800ms)

 

3) 공간복잡도

N이 10만으로 많이 크지 않아 고려하지 않음

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

분할정복 코드 작성법

 

Java 코드 : 

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

// 2342 Dance Dance Revolution
public class Main {

	static ArrayList<Integer> input; // 스텝이 총 몇개인지 모름
	// dp[ i ] [ j ] [ k ] : 왼발(j) 위치, 오른발(k) 위치이고 - i번째 스텝일때 최댓값
	static int[][][] dp; // [ i ] <= 10만
	static int N;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

		input = new ArrayList<Integer>();
		for (;;) {
			int in = Integer.parseInt(st.nextToken());
			if (in==0) break;
			input.add(in);
		}

		N = input.size();
		dp = new int[N+1][5][5];
		
		int ans = DDR(0, 0, 0);
		bw.write(ans + "\n");

		bw.flush();
		bw.close();
		br.close();
	}

	static int DDR(int step, int left, int right) {
		// 1. 마지막 스텝 도달하면 끝
		if (step == N)
			return 0;

		// 2. dp에 값이 차있으면 return
		if (dp[step][left][right] != 0) {
			return dp[step][left][right];
		}

		// 3. 가능한 경우의 수 중 가장 적은 경우로 갱신하고 return
		// 왼발 욺직이는 경우 vs 오른발 움직이는 경우
		int leftScore = score(left, input.get(step)) + DDR(step + 1, input.get(step), right); 
		int rightScore = score(right, input.get(step)) + DDR(step + 1, left, input.get(step)); 
		
		return dp[step][left][right] = Math.min(leftScore, rightScore);
	}

    static int score(int from, int to){
    	// 0. 지금 위치를 누르면 1
    	if(from==to) return 1;
    	// 1. 가운데 출발 2
        if(from==0) return 2;
        // 3. 크로스 해서 밟으면 4
        if(Math.abs(from-to) ==2) return 4;
        // 4. 인접 스텝 밟으면 3
        return 3;
    }
}