[c++] 백준 2342 - Dance Dance Revolution(dp, 메모이제이션)

0. [c++] 백준

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

1. 풀이

기본적인 동적 계획법을 활용한 문제로 메모이제이션을 활용하여 계산시간을 단축시켜 문제를 해결하였다.

발을 이동하는 것은 경우의 수에 따라 나눠주었다.

2. 소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int arr[100001];
int cache[100001][5][5];
int K;
const int INF = 1000000007;
 
int dp(const int& N = 0, const int& left = 0, const int& right = 0) {
    //기저 사례 : 범위를 벗어난 경우
    if (N == K)
        return 0;
    //메모이제이션 활용
    int& ret = cache[N][left][right];
    //기저 사례 : 이미 계산이 끝난 경우
    if (ret != 0)
        return ret;
 
    ret = INF;
    int next = arr[N];
 
    //왼쪽 발을 움직이는 경우
    if (left == next) 
        ret = min(dp(N + 1, left, right) + 1, ret);
    else if (next != right) 
        if (left == 0) 
            ret = min(dp(N + 1, next, right) + 2, ret);
        else 
            if (abs(left - next) == 1 || abs(left - next) == 3) 
                ret = min(dp(N + 1, next, right) + 3, ret);
            else 
                ret = min(dp(N + 1, next, right) + 4, ret);
 
    //오른쪽 발을 움직이는 경우
    if (right == next) 
        ret = min(dp(N + 1, left, right) + 1, ret);
    else if (next != left) 
        if (right == 0) 
            ret = min(dp(N + 1, left, next) + 2, ret);
        else 
            if (abs(right - next) == 1 || abs(right - next) == 3) 
                ret = min(dp(N + 1, left, next) + 3, ret);    
            else 
                ret = min(dp(N + 1, left, next) + 4, ret);
            
 
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int temp;
 
    while (1) {
        cin >> temp;
        if (temp == 0)
            break;
        arr[K++] = temp;
    }
 
    cout << dp() << endl;
 
 
    return 0;
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!