2342 Dance Dance Revolution

์•Œ๊ณ ๋ฆฌ์ฆ˜(DP)

1. ์™ผ๋ฐœ ์œ„์น˜, ์˜ค๋ฅธ๋ฐœ ์œ„์น˜, ๋ช…๋ น ๋ฒˆํ˜ธ๋ฅผ ๊ธฐ์ค€์œผ๋กœ dp ์ž๋ฃŒ๋ฅผ ๋งŒ๋“ฌ
	dp[5][5][MAX_COMMAND]
2. ๋ช…๋ น๊ณผ ๊ฐ™์€ ์นธ์— ์žˆ์„ ๊ฒฝ์šฐ ๊ทธ๋Œ€๋กœ, ๋‹ค๋ฅธ ์œ„์น˜์— ์žˆ์„ ๊ฒฝ์šฐ ๊ฐ€๋Šฅํ•œ ์œ„์น˜์—” ์ „๋ถ€ ์˜ฎ๊ธฐ๋Š” ์‹์œผ๋กœ DP ์‹œํ–‰.

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#define MAX_COMMAND 1000000
 
using namespace std;
 
int command[MAX_COMMAND];
int numOfCommand;
int foot[2];
int dp[5][5][MAX_COMMAND];
 
int getMinEnergy(int cmd);
int min(int a, int b) {
	return a < b ? a : b;
}
bool isClose(int f, int cmd);
bool isOpposite(int f, int cmd);
 
int main() {
	while (true) {
		cin >> command[numOfCommand];
		if (command[numOfCommand] == 0)
			break;
		numOfCommand++;
	}
 
	cout << getMinEnergy(0);
}
 
int getMinEnergy(int cmd) {
	if (cmd == numOfCommand)
		return 0;
	if (dp[foot[0]][foot[1]][cmd] != 0)
		return dp[foot[0]][foot[1]][cmd];
 
	int minimum = 2000000000;
	//๊ฐ™์€ ์ž๋ฆฌ์— ์žˆ๋Š” ๋ฐœ์ด ์žˆ๋Š”์ง€ ๊ฒ€์‚ฌ
	if (command[cmd] == foot[0] || command[cmd] == foot[1]) {
		minimum = min(minimum, getMinEnergy(cmd + 1) + 1);
	}
	else {
		//์ค‘์•™์— ์žˆ๋Š” ์ง€ ํ™•์ธ
		if (foot[0] == 0) {
			foot[0] = command[cmd];
			minimum = min(minimum, getMinEnergy(cmd + 1) + 2);
			foot[0] = 0;
		}
		if (foot[1] == 0) {
			foot[1] = command[cmd];
			minimum = min(minimum, getMinEnergy(cmd + 1) + 2);
			foot[1] = 0;
		}
 
		int tempLeft = foot[0];
		int tempRight = foot[1];
		//์ธ์ ‘ํ•œ์ง€ ํ™•์ธ
		if (isClose(foot[0], command[cmd])) {
			foot[0] = command[cmd];
			minimum = min(minimum, getMinEnergy(cmd + 1) + 3);
			foot[0] = tempLeft;
		}
		if (isClose(foot[1], command[cmd])) {
			foot[1] = command[cmd];
			minimum = min(minimum, getMinEnergy(cmd + 1) + 3);
			foot[1] = tempRight;
		}
		//๋ฐ˜๋Œ€ํŽธ์œผ๋กœ
		if (isOpposite(foot[0], command[cmd])) {
			foot[0] = command[cmd];
			minimum = min(minimum, getMinEnergy(cmd + 1) + 4);
			foot[0] = tempLeft;
		}
		if (isOpposite(foot[1], command[cmd])) {
			foot[1] = command[cmd];
			minimum = min(minimum, getMinEnergy(cmd + 1) + 4);
			foot[1] = tempRight;
		}
	}
	return dp[foot[0]][foot[1]][cmd] = minimum;
}
 
bool isClose(int f, int cmd) {
	if (f == 1 && (cmd == 2 || cmd == 4))
		return true;
	if (f == 2 && (cmd == 1 || cmd == 3))
		return true;
	if (f == 3 && (cmd == 2 || cmd == 4))
		return true;
	if (f == 4 && (cmd == 1 || cmd == 3))
		return true;
	return false;
}
 
bool isOpposite(int f, int cmd) {
	if (f == 1 && cmd == 3)
		return true;
	if (f == 2 && cmd == 4)
		return true;
	if (f == 3 && cmd == 1)
		return true;
	if (f == 4 && cmd == 2)
		return true;
	return false;
}