[백준 알고리즘] 2342번 Dance Dance Revolution 문제풀이 c++

처음에 DFS로 풀었으나 시간초과로 틀렸다. DP문제는 해도해도 헷갈린다ㅜ

 

dp[n][i][j]는 n번째 움직임에서 왼쪽발이 i에 있고, 오른쪽이 j에 있을때 power의 최솟값을 뜻한다.

1번째 움직임에서 가능한 경우는 왼발이 moves[1]에 있거나 오른발이 moves[1]에 있을 때이다.

따라서 dp의 초기값은 dp[1][moves[1]][0] = 2, dp[1][0][moves[1]] = 2이다. (0에서 이동한 경우엔 power가 2)

2~n까지 탐색을 통해 dp값을 채우면 dp[n]의 최솟값이 구하고자하는 power의 최솟값이다.

 

양발은 같은 위치에 있으면 안 되므로 if(moves[x] !=i) , if(moves[x] !=j)로 확인한다.

 

x1-> x2의 이동의 power계산은 scores[x1][x2]를 확인하도록 scores배열을 선언했다. 

#include <iostream>

using namespace std;

int dp[100001][5][5];
int moves[100001];
int scores[5][5] = {{0,2,2,2,2},{0,1,3,4,3},{0,3,1,3,4},{0,4,3,1,3},{0,3,4,3,1}};

int main(){
	int n = 1;
	while(1){
		cin >> moves[n];
		if(moves[n++] == 0){
			break;
		}
	}
	dp[1][0][moves[1]] = 2;
	dp[1][moves[1]][0] = 2;
	
	for(int x=2; x<=n; x++){
		for(int i=0; i<5; i++){
			for(int j=0; j<5; j++){
				if(dp[x-1][i][j] != 0){
					if(moves[x] != j)
						if(dp[x][moves[x]][j] == 0)
							dp[x][moves[x]][j] = dp[x-1][i][j] + scores[i][moves[x]];
						else
							dp[x][moves[x]][j] = min(dp[x][moves[x]][j], dp[x-1][i][j] + scores[i][moves[x]]);
					if(moves[x] != i)
						if(dp[x][i][moves[x]] == 0)
							dp[x][i][moves[x]] = dp[x-1][i][j] + scores[j][moves[x]];			
						else
							dp[x][i][moves[x]] = min(dp[x][i][moves[x]], dp[x-1][i][j] + scores[j][moves[x]]);
				}
			}
		}
	}
	int res = 400001;
	for(int i=0; i<5; i++){
		for(int j=0; j<5; j++){
			if(dp[n][i][j] != 0)
				res = min(res,dp[n][i][j]);
		}
	}
	if(res == 400001)
		res = 0;
	cout << res;
	return 0;
}