[백준 - 2342번] Dance Dance Revolution - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: dp

입력

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

출력

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

풀이

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

완탐은 각 턴마다 지수 승으로 증가하기 때문에 불가능하다.

매 턴마다 비용이 적게 드는 선택이 최선의 선택이 아닐 수 있기 때문에 그리디도 아니다.

그래서 이 문제는 dp를 활용해서 풀어야 한다.

생각해 보면 각 턴마다 왼발과 오른발의 위치는 총 21가지 존재한다.

이 말은 각 턴마다 경우의 수는 최대 21가지로 유지할 수 있음을 의미한다.

그래서 dp[A][B][C]는 -> A는 현재 턴을 의미하고, B는 왼발의 위치, C는 오른발의 위치로 정의할 수 있다.

각 턴마다 전 턴에서 목표 위치로 움직일 경우를 나눠서 현재 턴을 업데이트 해준다.
예를 들어 3번째 턴일 때 전 턴에서 dp[2][1][2]가 존재하는 경우 다음과 같은 경우로 나눠줄 수 있다.

• 현재 턴에서 목표 위치를 밟고 있는 경우 ex) 1이나 2
  • dp[3][1][2] = Math.min(dp[3][1][2], dp[2][1][2] + 1)
• 현재 턴에서 목표 위치를 밟고 있지 않은 경우 ex) 3
  • 왼발을 목표 위치로 움직이는 경우 dp[3][3][2] = Math.min(dp[3][3][2], dp[2][1][2] + 4); 인접하지 않기 때문에 4를 더해줌.
  • 오른발을 목표 위치로 움직이는 경우 dp[3][1][3] = Math.min(dp[3][1][3], dp[2][1][2] + 3); 인접하기 때문에 3를 더해줘야 됨.

이 풀이의 시간 복잡도는 O(10만 * 21)이다.

소스 코드

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

public class Main {
    static final int MAX = 500000;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      ArrayList<Integer> turnList = new ArrayList<>();
      int ct = Integer.parseInt(st.nextToken());
      while(ct != 0) {
          turnList.add(ct);
          ct = Integer.parseInt(st.nextToken());
      }
      int[][][] dp = new int[turnList.size() + 1][5][5];//[A][B][C] -> A는 턴, B는 왼쪽 다리 위치, C는 오른쪽 다리 위치
      for(int i=0; i<=turnList.size(); i++) {
          for(int j=0; j<=4; j++) {
              for(int k=0; k<=4; k++) {
                  dp[i][j][k] = MAX;
              }
          }
      }
      
      dp[0][0][0] = 0;
      for(int i=1; i<=turnList.size(); i++) {
          int nextMove = turnList.get(i - 1); // 움직여야될 위치
          for(int j=0; j<=4; j++) {
              for(int k=0; k<=4; k++) {
                  if(dp[i -1][j][k] != MAX) {
                      //가능한 경우
                      if(j == nextMove || k == nextMove) {
                          //왼, 오른이 이미 가야될 위치에 있는 경우
                          dp[i][j][k] = Math.min(dp[i][j][k], dp[i - 1][j][k] + 1);
                      } else {
                          //그게 아니라면 왼이나 오른을 가야될 위치로 움직인다.
                          //왼
                          int lp = findPower(j, nextMove); //왼쪽이 움직이는데 드는 힘
                          dp[i][nextMove][k] = Math.min(dp[i][nextMove][k], dp[i - 1][j][k] + lp);
                          //오른
                          int rp = findPower(k, nextMove); //오른쪽이 움직이는데 드는 힘
                          dp[i][j][nextMove] = Math.min(dp[i][j][nextMove], dp[i - 1][j][k] + rp);
                      }
                  }
              }
          }
      }
      
      int answer = MAX;
      for(int j=0; j<=4; j++) {
          for(int k=0; k<=4; k++) {
              answer = Math.min(answer, dp[turnList.size()][j][k]);
          }
      }
      System.out.println(answer);
  }
  
  static int findPower(int cur, int target) {
      if(cur == 0) {
          //중앙
          return 2;
      } else if(Math.abs(cur - target) == 2) {
          //반대편
          return 4;
      }
      return 3; //인접
  }
}