[백준/JAVA] 2342번: Dance Dance Revolution

🔺 문제

2342번: Dance Dance Revolution

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        // dp[N][L][R] : N개 수열을 수행했고, 왼쪽이 L. 오른쪽이 R에 있을 때 최소 누적 힘
        int dp[][][] = new int[100001][5][5];
        
        // 한 발 이동 시 드는 힘 미리 저장
        int mp[][] = {  {0, 2, 2, 2, 2},
                        {2, 1, 3, 4, 3},
                        {2, 3, 1, 3, 4},
                        {2, 4, 3, 1, 3},
                        {2, 3, 4, 3, 1}
                     };
                     
        int n = 0, s = 1;
        for(int i = 0 ; i < 5 ; i++) {
            for(int j = 0 ; j < 5 ; j++) {
                for(int k = 0 ; k < 100001 ; k++) {
                    dp[k][i][j] = 100001 * 4;   // 충분히 큰 수로 초기화
                }
            }
        }
        dp[0][0][0] = 0;    // 처음에는 아무 힘이 들지 않은 상태로 시작
        
        st = new StringTokenizer(br.readLine()," ");
        while(true) {
            n = Integer.parseInt(st.nextToken());
            
            if(n == 0)
                break;
            for(int i = 0 ; i < 5 ; i++) {
                if( n == i ) {  // 두 발이 같은 자리에 있을 수 없음
                    continue;
                }
                // 오른발을 옮겨 현재 모습이 됐을 때 최소 힘 저장
                for(int j = 0 ; j < 5 ; j++) {
                    dp[s][i][n] = Math.min(dp[s - 1][i][j] + mp[j][n], dp[s][i][n]);
                }
            }
            
            for(int j = 0 ; j < 5 ; j++) {
                if( n == j ) {  // 두 발이 같은 자리에 있을 수 없음
                    continue;
                }
                // 왼발을 옮겨 현재 모습이 됐을 때 최소 힘 저장
                for(int i = 0 ; i < 5 ; i++) {
                    dp[s][n][j] = Math.min(dp[s - 1][i][j] + mp[i][n], dp[s][n][j]);
                }
            }
            s++;
        }
        s--;
        
        int min = Integer.MAX_VALUE;
        for(int i = 0 ; i < 5 ; i++) {
            for(int j = 0 ; j < 5 ; j++) {
                min = Math.min(min, dp[s][i][j]);   // 모두 수행했을 때 최소값 찾기
            }
        }
        System.out.println(min);    // 최솟값 출력
    }
}

✅ 해결 아이디어
✔ 3차원 DP 테이블
- dp[N][L][R] : N개 수열을 수행했고, 왼쪽이 L. 오른쪽이 R에 있을 때 최소 누적 힘

 

알고리즘과 해설은... 아래 다른 풀이들이 더 잘 적어두셔서 링크 첨부로 대체...

 

---

🔺 다른 풀이들

- 과정 설명 최고! (복습용)

[백준] 2342 - Dance Dance Revolution

 

 

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

백준 2342번 Dance Dance Revolution

 

 

 

- 분할 정복으로 푸심

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

 

 

- Bottom-Up Top-Down 방식 모두 활용하심

[ BOJ ][JAVA][2342] Dance Dance Revolution

---

💬 느낀 점

3차원 DP 배열 이용하는 거는 ... 이제 익숙해져야하나 싶당,,,,ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V	7/7

 

 

(+7/7 2회독)

[ BOJ ][JAVA][2342] Dance Dance Revolution

해당 블로그 코드를 보고 제출했다... (Bottom-Up 방식)

개인적으로 첫 번째로 올려둔 코드보다 얘가 더 이해하기 좋았다.

근데 아직 혼자 풀라면 못 풀겠어서 77번 더 복습해야할듯,,,,😳

import java.util.*;
import java.io.*;
 
public class Main {
    static int INF = 987654321;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        List<Integer> list = new ArrayList<>();
        list.add(0);
        
        while(true) {
            int num = Integer.parseInt(st.nextToken());
            if(num == 0)    break;
            list.add(num);        
        }
        
        int len = list.size();
        int[][][] dp = new int[len][5][5];
        for(int k = 0 ; k < len ; k++) {
            for(int i = 0 ; i < 5 ; i++) {
                for(int j = 0 ; j < 5 ; j++) {
                    dp[k][i][j] = INF;
                }
            }
        }
        dp[0][0][0] = 0;
        
        for(int idx = 0 ; idx < len - 1 ; idx++) {
            int next = list.get(idx + 1);
            
            for(int i = 0 ; i < 5 ; i++) {
                for(int j = 0 ; j < 5 ; j++) {
                    int now = dp[idx][i][j];
                    
                    if(next != j) {
                        dp[idx + 1][next][j] = Math.min(dp[idx + 1][next][j], now + solve(i, next));
                    }
                    if(next != i) {
                        dp[idx + 1][i][next] = Math.min(dp[idx + 1][i][next], now + solve(j, next));
                    }
                }
            }
        }
        
        int ans = Integer.MAX_VALUE;
        for(int i = 0 ; i < 5 ; i++) {
            for(int j = 0 ; j < 5 ; j++) {
                ans = Math.min(ans, dp[len - 1][i][j]);
            }
        }
        
        System.out.println(ans);
    }
    
    private static int solve(int l, int r) {
        if(l == r)      return 1;               // 같은 지점 : 1
        else if(l == 0) return 2;               // 중심 -> 다른 : 2
        else if(Math.abs(l - r) == 2) return 4;   // 반대편 : 4
        else return 3;                          // 다른 -> 인접 : 3
    }
}
 

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편