백준 2343 Dance Dance Revolution

 

dp 문제입니다. 각 지시사항때 두 발의 위치를 각각 인덱스로 주면 해결 할 수 있습니다.

 

즉 dp[i][j][k] = i지시사항때 왼발이 j 오른발이 k 라고 생각하시면 됩니다. 이후 각 함수마다 

 

다음 지시사항을 왼발을 이용해서 진행할지 오른발을 이용해서 진행할지 처리해주시면 해결이 됩니다.

 

아래는 코드입니다.

 

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>

#define INF 987654321
using namespace std;

int arr[100010];
int dp[100010][5][5]; //i번째 지시사항때 두발의 위치에 따른 사용힘
int idx;

int sol(int left, int right, int cnt) {
			
	if(cnt == idx) {				
		return 0;
	}
	
	int& ret = dp[cnt][left][right];
	if(ret != -1) return ret;
	ret = INF;
	
		
	int plus;
	if (left == arr[cnt]) plus = 1;
	else if (left == 0) plus = 2;
	else if (abs(left - arr[cnt]) == 2) plus = 4;
	else plus = 3;	
	
	ret = min(ret ,sol(arr[cnt], right, cnt+1)+plus);
	
	if (right == arr[cnt]) plus = 1;
	else if (right == 0) plus = 2;
	else if (abs(right - arr[cnt]) == 2) plus = 4;
	else plus = 3;	
	
	ret = min(ret, sol(left, arr[cnt], cnt+1)+plus);
	
	return ret;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	memset(dp,-1,sizeof(dp));

	int x;	
	while (1) {
		cin >> x;
		if (x == 0) break;
		arr[idx++] = x;
	}	

	cout<<sol(0, 0, 0);
	return 0;
}