백준 2342번 - Dance Dance Revolution

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

2342번: Dance Dance Revolution

 

• 필요한 배경지식

다이나믹 프로그래밍

 

 

 

 

• 문제 해결 방법

3차원 배열을 사용하여 DP로 문제를 해결했습니다.

[1,4] 범위의 수가 N만큼 주워질때 배열 dp[n][x][y] = k에 대한 의미는 다음과 같습니다.

 

n의 범위: [0,N]

x, y의 범위: [0,4]

k: n번째 수까지 입력 받았을때, 두 발의 위치가 x, y인 경우에 사용된 최소의 힘

 

위와 같이 정의한다면 입력받은 i번째 수가 n인경우 다음과 같이 점화식을 세울 수 있습니다.

 

i-1번째 수에서의 왼발과 오른발의 위치가 각각 x,y일때

오른발이 y에서 n으로 이동한 경우 : dp[i][x][n] = min(dp[i][x][n], dp[i-1][x][y] + 필요한 힘);
왼발이 x에서 n으로 이동한 경우 : dp[i][n][y] = min(dp[i][n][y], dp[i-1][x][y] + 필요한 힘);

 

위치 a에서 b로갈때 필요한 힘의 계산은 calDist함수에 구현되어 있습니다.

 

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int n, i;
int dp[100001][5][5]{};

int calDist(int a, int b){ // a -> b
    if(a==b) return 1;
    if(a==0) return 2;
    a--, b--;
    if((a+1)%4==b || (a+3)%4==b) return 3;
    else if((a+2)%4 == b) return 4;
    else return INF;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0] = 0;

    for(i=1; ; i++){
        cin>>n;
        if(n==0) break;
        for(int x=0; x<5; x++) {
            for(int y=0; y<5; y++){
                if(dp[i-1][x][y]>=INF) continue;
                int a = calDist(x,n);
                int b = calDist(y,n);
                dp[i][x][n] = min(dp[i][x][n], dp[i-1][x][y] + b); // y -> n
                dp[i][n][y] = min(dp[i][n][y], dp[i-1][x][y] + a); // x -> n
            }
        }
    }

    i--;
    int ans = INF;
    for(int x=0; x<5; x++){
        for(int y=0; y<5; y++){
            ans = min(ans, dp[i][x][y]);
        }
    }
    cout<<ans;
}