백준 2342번 : Dance Dance Revolution

문제 링크 : www.acmicpc.net/problem/2342

내 풀이(2021.2.1.) :

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

vector<vector<vector<int>>> dp(100001, vector<vector<int>>(5, vector<int>(5, INT_MAX)));
int score[5][5] = {
	{INT_MAX,2,2,2,2},
	{INT_MAX,1,3,4,3},
	{INT_MAX,3,1,3,4},
	{INT_MAX,4,3,1,3},
	{INT_MAX,3,4,3,1}
};

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

	dp[0][0][0] = 0;
	int i = 1;
	while (1) {
		int cur; cin >> cur;
		if (cur == 0) {
			int ans = INT_MAX;
			for (int L = 0; L < 5; L++) {
				for (int R = 0; R < 5; R++) {
					ans = min(ans, dp[i - 1][L][R]);
				}
			}
			cout << ans;
			break;
		}

		// dp[i][L][R]

		// Move Right
		for (int L = 0; L < 5; L++) {
			for (int R = 0; R < 5; R++) {
				if (dp[i - 1][L][R] != INT_MAX && score[R][cur] != INT_MAX)
					dp[i][L][cur] = min(dp[i][L][cur], dp[i - 1][L][R] + score[R][cur]);
			}
		}

		// Move Left
		for (int R = 0; R < 5; R++) {
			for (int L = 0; L < 5; L++) {
				if (dp[i - 1][L][R] != INT_MAX && score[L][cur] != INT_MAX)
					dp[i][cur][R] = min(dp[i][cur][R], dp[i - 1][L][R] + score[L][cur]);
			}
		}

		i++;
	}

	return 0;
}