백준 2342 : Dance Dance Revolution(GOLD III)

dp문제다. 그것도 3차원

어떻게 어찌어찌 하다 보니까 맞았던 문제다.

#include<iostream>
#include<vector>
using namespace std;
long long int a, dp[100000][5][5], minn=5;
int min1, min2;
vector<int> v;
int dis(int a, int b){
	if(a==0 or b==0) return 2;
	if(a==b) return 1;
	if(abs(a-b)==2) return 4;
	else return 3;
}
int main(){
	while(cin >> a){
		if(a==0) break;
		v.push_back(a);
	}
	if(v.size()==0){
		cout << "0";
		return 0;
	}// default
	for(int i=0;i<v.size();i++){
		for(int j=0;j<=4;j++){
			for(int k=0;k<=4;k++) dp[i][j][k]=1e6;
		}
	} // for distancewise correction
	dp[0][v[0]][0]=2;
	for(int i=1;i<v.size();i++){
		for(int j=0;j<=4;j++){
			min1=1e6, min2=1e6;
			for(int k=0;k<=4;k++){
				if(j==k) continue;
				if(min1>dp[i-1][k][j]+dis(k, v[i])) min1=dp[i-1][k][j]+dis(k, v[i]);
				if(min2>dp[i-1][j][k]+dis(k, v[i])) min2=dp[i-1][j][k]+dis(k, v[i]);
			}
			dp[i][v[i]][j]=min1;
			dp[i][j][v[i]]=min2; 
		}
	}
	int N=v.size()-1, minn=1e6;
	for(int i=0;i<=4;i++){
		for(int j=0;j<=4;j++){
			if(i==j) continue;
			if(minn>dp[N][i][j]) minn=dp[N][i][j];
		}
	}
	cout << minn;
}

다음은 너다 ACM CRAFT