[백준 2342번] Dance Dance Revolution (C++)

문제링크 : https://www.acmicpc.net/problem/2342

2342번: Dance Dance Revolution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int dp[100001][5][5];
vector<int>v;

int move(int a, int b)
{
    if(a==b) return 1; //똑같은 위치로 이동
    else if(a==0) return 2; //중앙에서 이동
    else if(abs(a-b)==2) return 4; //반대편으로 이동
    else return 3; //인접한 부분으로 이동
}

int func(int l, int r, int idx)
{
    if(idx==v.size()) return 0; //전부 탐색하면 종료
    if(dp[idx][l][r]!=0) return dp[idx][l][r]; //시간초과 방지
    int Left = func(v[idx], r, idx + 1) + move(l, v[idx]); //왼쪽발 이동
    int Right = func(l, v[idx], idx + 1) + move(r, v[idx]); //오른쪽발 이동
    return dp[idx][l][r] = min(Left, Right); //왼발 오른발 중 최솟값 저장
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N;
    while(1)
    {
        cin >> N;
        if(N==0) break;
        v.push_back(N);
    }
    cout << func(0, 0, 0);

    return 0;
}

중앙에서 발을 이동시킬 때 왼발이 이동하는지, 오른발이 이동하는지에 주의해야 한다.

방법이 위와 같이 2가지 이므로 2가지에 대해서 move를 진행해주고 최소값을 찾는 문제이기 때문에 반환값이 더 작은 값을 선택하여 현재 dp에 저장해준다.

 

move 함수에서 반환하는 값은 문제에서 주어진 조건에 따라서 같은 위치로 이동하는지, 중앙에서 다른 곳으로 이동하는지, 반대편으로 이동하는지, 인접한 부분으로 이동하는지 체크를 해주고 이에 맞게 반환해주면 된다.

위에서 반환받은 값이 곧 이동시간이 되고 이어서 탐색하기 위해 idx의 값을 1증가시켜서(탐색할 값 이동) func 함수에 다시 넣어준다.

이때 변경된 위치인 v[idx]의 값을 이동한 발에 따라서 (v[idx], r : 왼쪽 이동), (l, v[idx] : 오른쪽 이동) 적절한 값을 넣어준다.

 

idx의 값이 v.size()와 같아진다면 모든 탐색을 마친 것이게 return 0을 해줌으로써 종료해준다.

그리고 주의해야 할 것은 현재 탐색할 dp의 값이 0이 아니라면 이는 이미 탐색하여 값을 저장한 값이라는 것이다.

이 경우에는 이미 값이 있기에 바로 반환을 해주어야하며, 반환을 안해주면 이미 탐색한 값을 다시 탐색함에 따라 시간초과가 발생한다.