[백준 C++] 2342 Dance Dance Revolution - 다이나믹프로그래밍

2342번: Dance Dance Revolution

#include <iostream>
#include <climits>
using namespace std;

const int Infinite = INT_MAX;
const int MoveCost[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 DP[100000][5][5];

void Init()
{
	for (int i = 0; i < 100000; ++i)
	{
		for (int Left = 0; Left < 5; ++Left)
		{
			for (int Right = 0; Right < 5; ++Right)
			{
				DP[i][Left][Right] = Infinite;
			}
		}
	}
}

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

	Init();
	int Cnt = 0;

	int NewLoc;
	cin >> NewLoc;
	DP[Cnt][0][NewLoc] = 2;
	++Cnt;
	while (true)
	{
		cin >> NewLoc;
		if (NewLoc == 0)
		{
			break;
		}

		for (int Left = 0; Left < 5; ++Left)
		{
			for (int Right = 0; Right < 5; ++Right)
			{
				int PrevCost = DP[Cnt - 1][Left][Right];
				if (PrevCost == Infinite)
				{
					continue;
				}

				int Cost = Infinite;

				// Right
				Cost = DP[Cnt][Left][NewLoc];
				Cost = min(Cost, PrevCost + MoveCost[Right][NewLoc]);
				DP[Cnt][Left][NewLoc] = Cost;

				// Left
				Cost = DP[Cnt][NewLoc][Right];
				Cost = min(Cost, PrevCost + MoveCost[Left][NewLoc]);
				DP[Cnt][NewLoc][Right] = Cost;
			}
		}

		++Cnt;
	}

	int Min = Infinite;
	for (int Left = 0; Left < 5; ++Left)
	{
		for (int Right = 0; Right < 5; ++Right)
		{
			Min = min(Min, DP[Cnt - 1][Left][Right]);
		}
	}

	cout << Min;
}

---

 

다이나믹 프로그래밍 유형의 문제입니다.

각 지시 사항마다, 왼발을 움직였을 때와 오른발을 움직였을 때의 누적 힘을 DP 배열에 모두 저장해서 풀었습니다.

 

이전 지시 사항에서 현재 지시 사항으로 넘어오면서

현재 지시 사항에 해당하는 위치를 왼발로 시행했을 때, 오른발로 시행했을 때 각각 누적되는 힘을 저장하도록 했습니다.