[C++] 백준 2342 Dance Dance Revolution

#include <iostream>
#include <vector>
 
std::vector<int> vec = {};
int dp[5][5][100001] = {};
 
int move(int cur, int next)
{
    if (cur == next)
        return 1;
 
    else if (!cur)
        return 2;
 
    else if (abs(cur - next) == 2)
        return 4;
 
    return 3;
}
 
int DFS(int left, int right, int index) 
{
    if (index >= vec.size())
        return 0;
 
    int& next = dp[left][right][index];
 
    if (next)
        return next;
 
    next = std::min(move(left, vec[index]) + DFS(vec[index], right, index + 1),
        move(right, vec[index]) + DFS(left, vec[index], index + 1));
 
    return next;
}
 
int main() 
{
    int N = 0;
    while (true) 
    {
        std::cin >> N;
        if (!N)
        {
            break;
        }
 
        vec.push_back(N);
    }
 
    std::cout << DFS(0, 0, 0);
 
    return 0;
}
 

 

처음엔 왼쪽이든 오른쪽이든 한쪽으로 무조건 3일 줄 알았는데 4도 나오더라...

결국엔 예전에 풀어본 3가지 길로 풀었던 것처럼 왼쪽이랑 오른쪽으로 나눠서 계속해서 길을 계산해가면서 풉니다.

완전 탐색과 비슷하지만 계싼해가면서 가장 짧은 길을 구해서 갑니다.