[2342번][C/C++] Dance Dance Revolution

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

2342번: Dance Dance Revolution

 "Dance Dance Revolution" 일명 DDR을 플레이할 때, 왼발과 오른발의 위치에 따라 다음 버튼을 누르는데 소비하는 에너지가 다르다면  눌러야하는 버튼이 순서대로 주어졌을 때, 가장 적은 에너지로 버튼을 누를 수 있는 에너지를 구하는 문제이다.

 

일단 비슷한 문제가 하나 생각나는데 [2618번]경찰차 문제가 생각난다.

하지만 이 문제가 더 단순화된 버전이다.

 

왼발과 오른발의 위치에 따라 다음 버튼들을 누르는데 드는 에너지의 값이 달라진다.

따라서 지금 내가 왼발로 누르는 것과 오른발로 누르는 것중 무엇이 최선의 선택인지 모든 경우를 탐색하기 전에는 알 수 없다.

따라서 이 문제는 기본적으로 완전탐색에 DP를 이용해서 시간복잡도를 줄이는 문제이다.

 

DP는 중복된 계산이 이뤄질 때 값을 저장해뒀다가 사용하는 기법이다.

그렇다면 이 문제에서는 어떤 부분에서 중복된 계산이 이뤄질까?

바로 다음 버튼을 누르기 전에 왼발이 있는 위치와 오른발이 있는 위치를 이미 계산한 경우이다.

이 경우에는 이 이후의 계산 값들이 똑같을 것임을 알 수 있다.

즉 왼쪽발과 오른쪽발의 위치가 이미 계산한 적 있는 위치라면 다시 계산하지 않는 것이다.

 

3차원 DP배열을 선언해서 해결했다.

DP[ i 번째 버튼 ][ 현재 왼발 ][ 현재 오른발 ] = i 번째 버튼을 포함해서 이 이후의 버튼을 누르는 값들의 합의 최솟값

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <utility>

#define INF 987654321

using namespace std;

int cmds[100002];
int dp[100002][5][5];
int idx = 1;

int calc(int cur, int next) {
    if(cur == 0) {
        if(next == 1) return 2;
        else if(next == 2) return 2;
        else if(next == 3) return 2;
        else if(next == 4) return 2;
    }
    else if(cur == 1) {
        if(next == 1) return 1;
        else if(next == 2) return 3;
        else if(next == 3) return 4;
        else if(next == 4) return 3;
    }
    else if(cur == 2) {
        if(next == 1) return 3;
        else if(next == 2) return 1;
        else if(next == 3) return 3;
        else if(next == 4) return 4;
    }
    else if(cur == 3) {
        if(next == 1) return 4;
        else if(next == 2) return 3;
        else if(next == 3) return 1;
        else if(next == 4) return 3;
    }
    else {
        if(next == 1) return 3;
        else if(next == 2) return 4;
        else if(next == 3) return 3;
        else if(next == 4) return 1;
    }
}

int solve(int cnt, int left, int right) {
    if(dp[cnt][left][right] != INF) return dp[cnt][left][right];
    if(cnt == idx - 1) return 0;

    return dp[cnt][left][right] = min(calc(left, cmds[cnt+1]) + solve(cnt+1, cmds[cnt+1], right), calc(right, cmds[cnt+1]) + solve(cnt+1, left, cmds[cnt+1]));
}

void init() {
    for(int i=0;i<100002;i++) {
        for(int j=0;j<5;j++) {
            dp[i][j][0] = INF;
            dp[i][j][1] = INF;
            dp[i][j][2] = INF;
            dp[i][j][3] = INF;
            dp[i][j][4] = INF;
        }
    }
}

int main() {
    int inp;

    init();

    do {
        scanf("%d", &inp);
        cmds[idx++] = inp;
    } while(inp != 0);
    idx--;

    solve(0, 0, 0);

    printf("%d", dp[0][0][0]);

    return 0;
}