[백준] 알고리즘 분류(다이나믹 프로그래밍,JAVA)2342번, Dance Dance Revolution

문제 링크

2342번: Dance Dance Revolution

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. DDR은 하나의 중점을 기준으로 상하좌우  연결되어 있습니다.

2. 각 방향은 중점(0), 위(1), 왼쪽(2), 아래(3), 오른쪽(4)으로 표현한다.

3. 시작을 제외하고 두 발은 같은 발판에 존재할 수 없습니다.

4. 발을 중앙에서 움직이면 2, 중앙이 아닌 발판에서 인접한 발판으로 움직이면 3, 동일한 발판을 누르면 1의 힘이 듭니다.

5.발판을 누르는 순서가 주어질 때, 사용되는 최소의 힘을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 발을 발판에 놓인 경우를 구분하도록 DP[][][]를 구성하여 탐색합니다.

 

3. 탐색이 끝나고 얻은 최소 힘을 결과로 출력합니다.

 

각 발이 놓인 발판에 따른 DP탐색!

 

발판을 밟을 때 취하는 행동 2가지 경우

 

1. 왼발로 다음 발판 밟기

 

2. 오른발로 다음 발판 밟기

 

발판을 밟을 때 드는 힘

 

저는 각 발판에 드는 힘을 2차원 배열로 정리해서 사용하였습니다.

width[i][j] :  i 발판에서 j발판으로 이동할 때 드는 힘

 

	0	1	2	3	4
0	0	2	2	2	2
1	0	1	3	4	3
2	0	3	1	4	3
3	0	4	3	1	3
4	0	3	4	1	3

 

DP[][][]탐색

 

 

위 그림처럼 발판을 밟는 방법이 퍼져나아가며, 중복된 탐색을 방지하기 위해서 DP[][][]를 사용합니다.

 

사용하는 힘

 

왼발 : l

오른발 : r

다음 발판 : nxt

 

왼발 ▶ 다음 발판 : width[l][nxt]

오른발 ▶ 다음 발판 : width[r][nxt]

 

재귀를 이용한 탐색을 통해서 모든 경우를 탐색한 뒤 최소 힘을 결과로 출력합니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

1 2 2 4 0

 

2. 각 발을 발판에 놓인 경우를 구분하도록 DP[][][]를 구성하여 탐색합니다.

 

DP[] 탐색!

 

 

최소 힘 : DP[0][0][0] = DP[1][0][1] ▶ DP[2][2][1] ▶ DP[3][2][1] ▶ DP[4][2][4]

 = 2 + 2 + 1 + 3 = 8

 

 

3. 탐색이 끝나고 얻은 최소 힘을 결과로 출력합니다.

 

DP[0][0][0] = DP[1][0][1] ▶ DP[2][2][1] ▶ DP[3][2][1] ▶ DP[4][2][4] : 8

 

8 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 발판 밟는 정보를 띄어쓰기 기준 나누었습니다.
• search함수을 통해 DP[][][]에 최소힘을 저장합니다.
• 탐색으로 얻은 최소힘(DP[0][0][0])을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 재귀로 발판을 밟는 2가지 경우를 통해 DP[][][]를 구성합니다.

 

결과코드

 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Main {
    //DP[i][j][k]
    //i : 현재 발판 인덱스
    //j : 왼발 현재 발판
    //k : 오른발 현재 발판
    static int[][][] DP;
    static ArrayList<Integer> list;	//밟는 발판 순서 저장 리스트
    static int size;
    //각 발판 이동할 때 드는 힘 저장 배열
    static int[][] width = { 
            {1, 2, 2, 2, 2}, 
            {0, 1, 3, 4, 3}, 
            {0, 3, 1, 3, 4}, 
            {0, 4, 3, 1, 3}, 
            {0, 3, 4, 3, 1}
    };
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        list = new ArrayList<>();
        //발판 밟는 순서 저장
        while (true) {
            int n = Integer.parseInt(st.nextToken());
            if (n == 0)
                break;
            list.add(n);
        }
        size = list.size();
        DP = new int[size][5][5];
        int answer = search(0, 0, 0);		//DP[][][] 재귀를 이용한 탐색 진행
        bw.write(String.valueOf(answer));	//최소 힘 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //재귀를 통해 DP[][][]를 구성하는 함수
    //idx : 현재 발판 인덱스, l : 왼발 , r : 오른발
    private static int search(int idx, int l, int r) {
        if(idx == size)	//발판 모두 밟았을 때
            return 0;

        if(DP[idx][l][r] != 0)	//이미 밟아본 발판일 경우
            return DP[idx][l][r];

        int nxt = list.get(idx);
        //search(idx+1, nxt, r) + width[l][nxt]) : 왼발로 다음 발판 밟기
        //search(idx+1, l, nxt) + width[r][nxt]) : 오른발로 다음 발판 밟기
        DP[idx][l][r] = Math.min(search(idx+1, nxt, r) + width[l][nxt],  search(idx+1, l, nxt) + width[r][nxt]);

        return DP[idx][l][r];
    }
}