백준 2342 Dance Dance Revolution [자바]

in Develop / Solving

문제 풀고 글쓰는거 까먹을 뻔 했다…

문제 분석

  • DDR 게임을 한다.
  • 게임에서 각 칸에 해당한는 숫자는 아래 그림과 같다.
  • 왼발, 오른발이 모두 0을 밟은 상태로 시작한다.
  • 발을 옮길 때는 힘을 소모하고, 각각의 상황에 소모하는 힘은 아래와 같다.
    • 0에서 다른 칸으로 움직일 때는 2의 힘을 소모한다.
    • 1, 2, 3, 4 에서 옆 칸으로 움직일 떄는 3을 소모.
    • 마주보는 수로 움직일 때는 4 소모.
    • 자기 자신을 다시 밟을 때는 1 소모.
  • 0을 제외하고 왼발, 오른발이 같은 칸에 있을 수 없음.

입력조건

밟을 숫자들 배열 + 끝에 0

풀이과정

문제를 처음 본 순간 ‘어 이거 dp 아니면 시간초과 나겠지?’ 라고 생각이 들었는데, 그러고 10초 뒤에 바로 ‘이걸 dp로 어떻게 풀지?’ 라는 생각이 들어버렸다.

  • 최초 입력받을 때, 반복할 횟수를 모른다고 생각하여서, 슬라이딩 윈도우를 사용해서 작은 크기의 배열을 채우고 비우며 dp를 작성하기로 하였다.
  • dp는 5*5크기의 배열로, r, c 값이 각각 왼발, 오른발을 나타낸다.
  • 게임을 시작하고 처음 만나는 숫자에 대해서는 2를 입력해 놓고 (a, 0), (0, a)
  • 그 다음부터는 dp를 이용한다.
  • dp 과정은 다음과 같다.
    • 이전에 밟았던 모든 칸들에 대해서(dp[ i-1 ]에서 값이 0이 아님.)
    • 왼발로 지금 칸을 밟는 경우와, 오른발로 지금 칸을 밟는 경우를 모두 고려한다.
    • 구해진 값들 중 제일 작은 값을 대입하며 배열을 완성한다.
  • 이렇게 하면, 밟을 수 없는 칸은 0으로 표시되며, 경우의 수가 하나라도 있는 칸은 숫자가 입력되며 dp배열이 완성된다.
  • 위의 방식으로 bottom-up 방식의 dp를 진행하였다.
PS

나는 bottom-up으로 풀었지만, top-down 형태로 푼 사람이 더 많은 거 같다.

코드 구성

  • 밟을 때 힘 계산

    static int getcost(int foot, int press) {
    int cost = 0;
  
    if(foot == 0) cost = 2;
    else if ( foot == press ) cost = 1;
    else if ( Math.abs(foot - press) == 2) cost = 4;
    else cost = 3;
  
    return cost;
}

  • dp

    // a가 지금 내가 밟아야 할 수
if(a != r) {
    if(dp[1][a][r] == 0) dp[1][a][r] = getcost(l, a) + dp[0][l][r];
    else				 dp[1][a][r] = Math.min(getcost(l, a) + dp[0][l][r], dp[1][a][r]);
}
  
// 오른발로 밟아보기
if(a != l) {
    if(dp[1][l][a] == 0) dp[1][l][a] = getcost(r, a) + dp[0][l][r];
    else				 dp[1][l][a] = Math.min(getcost(r, a) + dp[0][l][r], dp[1][l][a]);						
}
    • 코드가 if문으로 감싸진 것을 볼 수 있는데,
      이는 두 발이 같은 위치를 밟는 것을 방지한 것이다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.stream.Stream;

public class BJ2342_DDR {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[][][] dp = new int[2][5][5];
		int ini = Integer.parseInt(st.nextToken());
		if(ini == 0) {
			System.out.println(0); return;
		}
		dp[0][ini][0] = 2;
		dp[0][0][ini] = 2;
		
		while(true) {
			int a = Integer.parseInt(st.nextToken());
			if(a == 0) break;
			
			for(int l = 0; l < 5; l++) {
				for(int r = 0; r < 5; r++) {
					if(dp[0][l][r] == 0) continue;
					
					// 왼발로 밟아보기
					if(a != r) {
						if(dp[1][a][r] == 0) dp[1][a][r] = getcost(l, a) + dp[0][l][r];
						else				 dp[1][a][r] = Math.min(getcost(l, a) + dp[0][l][r], dp[1][a][r]);
					}
					
					// 오른발로 밟아보기
					if(a != l) {
						if(dp[1][l][a] == 0) dp[1][l][a] = getcost(r, a) + dp[0][l][r];
						else				 dp[1][l][a] = Math.min(getcost(r, a) + dp[0][l][r], dp[1][l][a]);						
					}
				}
			}
			// dp 끝.
			// 슬라이딩 윈도 정리
			for(int i = 0; i < 5; i++) {
				dp[0][i] = dp[1][i].clone();				
			}
			dp[1] = new int[5][5];
		}
		int min = 1000000;
		for(int i = 0; i < 5; i++) {
			for(int j = 0; j < 5; j++) {
				if(dp[0][i][j] == 0) continue;
				
				min = Math.min(min, dp[0][i][j]);
			}
		}
		System.out.print(min);
	}
	static int getcost(int foot, int press) {
		int cost = 0;
		
		if(foot == 0) cost = 2;
		else if ( foot == press ) cost = 1;
		else if ( Math.abs(foot - press) == 2) cost = 4;
		else cost = 3;
		
		return cost;
	}
}