<백준> 2342

Dance Dance Revolution

문제

입력
입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마지막을 의미한다. 즉, 입력 파일의 마지막에는 0이 입력된다. 입력되는 수열의 길이는 100,000을 넘지 않는다.

출력
한 줄에 모든 지시 사항을 만족하는 데 사용되는 최소의 힘을 출력한다.

int cost(int from, int to)
{
	if (from == to)
		return 1;
	if (from == 0)
		return 2;
	if (abs(from - to) == 2)
		return 4;
	return 3;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	vector<int> v;
	
	while (1)
	{
		int x;
		cin >> x;
		if (x == 0)
			break;
		v.push_back(x);
	}

	int dp[5][5];
	int temp[5][5];

	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			dp[i][j] = INT_MAX;
		}
	}

	dp[0][0] = 0;

	for (int next : v)
	{
		for (int i = 0; i < 5; i++)
		{
			for (int j = 0; j < 5; j++)
			{
				temp[i][j] = INT_MAX;
			}
		}
		for (int l = 0; l < 5; l++)
		{
			for (int r = 0; r < 5; r++)
			{
				if (dp[l][r] == INT_MAX)
					continue;
				temp[next][r] = min(temp[next][r], dp[l][r] + cost(l, next));
				temp[l][next] = min(temp[l][next], dp[l][r] + cost(r, next));
			}
		}
		memcpy(dp, temp, sizeof(dp));
	}

	int maxValue = INT_MAX;
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			maxValue = min(dp[i][j], maxValue);
		}
	}
	cout << maxValue;
}