[BOJ 2342] Dance Dance Revolution (C++)

Dance Dance Revolution (Gold 3)

문제

전체 문제 보기

2342번: Dance Dance Revolution

접근법

이번 문제는 동적 계획법을 재귀적으로 활용하여 풀어야 하기 때문에 다소 난이도가 있는 문제입니다. dp배열을 다음과 같이 설정하여 문제를 해결하였습니다.

• dp[idx][left][right]: idx번째 지시사항에서 ~ 마지막 지시사항까지 수행했을 때 왼발이 left, 오른발이 right일 때 필요한 에너지의 최솟값.

그리고 위치를 이동할때 소요되는 힘은 if문을 활용하여 매번 계산할 수도 있지만 다음과 같이 배열을 활용하여 사용할 수도 있습니다.

constexpr int cost[5][5] =
{
    {0,2,2,2,2},
    {0,1,3,4,3},
    {0,3,1,3,4},
    {0,4,3,1,3},
    {0,3,4,3,1}
};

전체 구현

다음과 같이 재귀함수 func을 구현하여 문제를 해결할 수 있습니다.

#include <iostream>
#include <array>
#include <algorithm>
int arr[100'000]{}, dp[100'000][5][5]{};
constexpr int cost[5][5] =
{
    {0,2,2,2,2},
    {0,1,3,4,3},
    {0,3,1,3,4},
    {0,4,3,1,3},
    {0,3,4,3,1}
};
constexpr int INF = 987'654'321;
int func(int idx, int left, int right, int tar)
{
    if (idx == tar) return 0;
    int& ret = dp[idx][left][right];
    if (ret != 0) return ret;

    ret = INF;
    const int nextCmd = arr[idx];
    if (nextCmd != left) // 왼발이 있는 곳으로 오른발을 옮길 수 없음. 
    { // 오른발을 옮기는 경우
        ret = std::min(ret, func(idx + 1, left, nextCmd, tar) + cost[right][nextCmd]);
    }
    if (nextCmd != right) // 오른발이 있는 곳으로 왼발을 옮길 수 없음
    { // 왼발을 옮기는 경우
        ret = std::min(ret, func(idx + 1, nextCmd, right, tar) + cost[left][nextCmd]);
    }

    return ret;
}
int main()
{
    //입출력 성능향상을 위한 설정
    std::ios_base::sync_with_stdio(false);
    std::cout.tie(NULL);
    std::cin.tie(NULL);

    int i = -1;
    do {
        i++;
        std::cin >> arr[i];
    } while (arr[i] != 0);

    int answer = func(0, 0, 0, i);
    std::cout << answer << std::endl;
    return 0;
}