[BOJ] 2342. Dance Dance Revolution

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

접근 방법

먼저 완전탐색을 이용해 재귀함수를 적용했다.

어차피 왼발, 오른발에 상태값은 0,1,2,3,4 로 고정되어있으니 무조건 재귀 함수를 불렀을 때 겹치는 결과가 나올 것이라 생각함. → 메모지에이션

현재있는 지점에서 어디로 갈 건지를 정하면서 left foot의 값에서 갈 지 right foot의 값에서 갈 지에 해당하는 힘을 추가해서 가장 최솟값을 구한다.

static int going(int go, int to){
        if(go==0) return 2;
        if(Math.abs(go-to) ==2) return 4;
        if(go==to) return 1;
        return 3;
    }

주의 사항

Need Know

1. DP

전체 코드 ( Java )

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[][][] dp;
    static ArrayList<Integer> map = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        set();
        solve();
        bw.flush();
        br.close();
        bw.close();
    }
    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        while(true){
            int k = Integer.parseInt(st.nextToken());
            if(k==0) break;
            map.add(k);
        }
        dp = new int[map.size()][5][5];
    }
    static void solve() throws IOException {
        bw.write(dfs(0,0,0)+"");
    }
    static int dfs(int x, int left, int right){
        if(x==map.size()){
            return 0;
        }
        if(dp[x][left][right] != 0){
            return dp[x][left][right];
        }

        int goLeft = dfs(x+1,map.get(x),right) + going(left,map.get(x));
        int goRight = dfs(x+1,left,map.get(x)) + going(right,map.get(x));

        return dp[x][left][right] = Math.min(goLeft, goRight);
    }
    static int going(int go, int to){
        if(go==0) return 2;
        if(Math.abs(go-to) ==2) return 4;
        if(go==to) return 1;
        return 3;
    }
}