2342. Dance Dance Revolution

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

2342번: Dance Dance Revolution

 

문제 설명

중앙(0), 상(1), 하(3), 좌(2), 우(4)로 된 발판이 있다. 두 발이 같은 지점에 있는 것을 불가능하다.

처음에 양발이 모두 중앙에 위치하고, 발을 이동시킬 때마다 cost가 발생한다.

중앙에서 네방향으로 갈 때 = 2

인접한 발판으로 갈 때 = 3

반대편 발판으로 갈때 = 4

그리고 같은 지점을 한번 더 누를 때는 1 cost가 발생한다.

 

지시 사항은 하나의 수열로 이루어지고 각각의 수열은 1, 2, 3, 4로 이루어져 있다. 이 숫자들은 각각의 방향을 나타낸다.

0은 수열의 마지막을 의미한다.

 

모든 지시 사항을 수행했을 때 최소 cost를 출력하는 문제이다.

 

 

문제 해결

(왼발, 오른발)로 표현한다고 하자.

만약 (2, 1)이라면 (1, 2)와 같은 상황임을 알 수 있다.

\( (a, b) \) 와 \( (b, a) \) 를 같은 상황이니 둘 중 하나는 빼고 나머지 모든 상황을 나열하면

(0, 1) (0, 2) (0, 3) (0, 4)

(1, 2) (1, 3) (1, 4)

(2, 3) (2, 4)

(3, 4)

이렇게 10가지 경우의 수가 나온다.

몇번을 하더라도 이 10가지 경우의 수 안에 들어오니 DP로 문제를 해결할 수 있다.

 

구현 편의 성을 위해서 \( (a, b) \) 와 \( (b, a) \) 를 다른 상황이라고 하고 DP를 진행하였는데,

그래도 최대 25가지의 경우의 수이므로 시간복잡도가 크게 증가하지 않아 큰 차이가 발생하지 않는다.

 

현재 \( (a, b) \) 에서 다음 지시 사항인 K가 들어온다고 하자. 이 때 나올 수 있는 경우의 수는 \( (K, b), (a, K) \) 두가지 이다.

그럼 현재까지의 cost인 \( dp[round][a][b] \) 와 \( a -> K \) 이동했을 때의 cost, \( b -> K\) 이동했을 때의 cost를 각 합을 구해 \( dp[round+1][K][b] \) 와 \( dp[round+1][a][K] \) 의 최소값을 갱신시킨다.

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
using nmp = map<pii, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
 
int getCost(int a, int b)
{
    if(a == 0) return 2;
    if(a == b) return 1;
    if(abs(a-b) == 2) return 4;
    return 3;
}
 
int dp[100001][5][5];
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
     
     memset(dp, -1, sizeof(dp));
     dp[0][0][0] = 0;
     int dpnum = 0;
    while(1)
    {
        int n;
        cin >> n;
        if(n == 0) break;
        for(int i=0;i<5;i++)
        {
            for(int j=0;j<5;j++)
            {
                if(dp[dpnum][i][j] == -1) continue;
                int lcost = dp[dpnum][i][j] + getCost(i, n);
                int rcost = dp[dpnum][i][j] + getCost(j, n);
                
                if(dp[dpnum+1][n][j] == -1) dp[dpnum+1][n][j] = lcost;
                else dp[dpnum+1][n][j] = min(lcost, dp[dpnum+1][n][j]);
 
                if(dp[dpnum+1][i][n] == -1) dp[dpnum+1][i][n] = rcost;
                else dp[dpnum+1][i][n] = min(rcost, dp[dpnum+1][i][n]);
            }
        }
        dpnum++;
    }
 
    int ans = INT_MAX;
    for(int i=0;i<5;i++)
    {
        for(int j=0;j<5;j++)
        {
            if(dp[dpnum][i][j] == -1) continue;
            ans = min(dp[dpnum][i][j], ans);
        }
    }
    cout << ans;
 
    return 0;
}