[ C++ 백준 2342 ] Dance Dance Revolution

DP 문제이다.

그냥 DP를 활용해서 전부 값을 찾았더니 해결되었다.

#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>
using namespace std;

const int MaxVal = 50000000;
int DP[100001][5][5] {}; //until 100000 | left 1,2,3,4 | right 1,2,3,4

int CalcCost(int start, int end)
{
	if (start == end)
		return 1;
	else if (start == 0)
		return 2;
	else if (start % 2 == 0)
	{
		if (end % 2 == 1)
			return 3;
		else
			return 4;
	}
	else if (start % 2 == 1)
	{
		if (end % 2 == 0)
			return 3;
		else
			return 4;
	}
		

	return MaxVal;
}

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

	memset(DP, 0x3f, sizeof(DP));
	DP[0][0][0] = 0;

	int input;

	for (int i = 1; ; ++i)
	{
		cin >> input;
		if (input == 0)
		{
			int ans = MaxVal;
			for (int left = 0; left < 5; ++left)
				for (int right = 0; right < 5; ++right)
				{
					ans = min(ans, DP[i - 1][left][right]);
				}
			cout << ans;
			return 0;
		};

		for(int left = 0; left < 5; ++left)
			for (int right = 0; right < 5; ++right)
			{
				if (DP[i - 1][left][right] == MaxVal) continue;
				int leftCost = CalcCost(left, input);
				int rightCost = CalcCost(right, input);
				DP[i][input][right] = min(DP[i][input][right], DP[i - 1][left][right] + leftCost);
				DP[i][left][input] = min(DP[i][left][input], DP[i - 1][left][right] + rightCost);
			}
	}


}

뭔가 계속 문제가 발생해서 찾아보니

memset에서 먼가 문제가 있는 것 같아서 메모리 초기화할 때 잘 사용한다는 0x3f를 넣었더니 해결되었다.