[백준/BOJ] 백준 2342번 : Dance Dance Revolution

https://www.acmicpc.net/problem/2342

2342번: Dance Dance Revolution

 

3차원 배열 cache에 cache[누를 순서][현재 왼발 위치][현재 오른발 위치] = "지금부터 끝까지 누르는데 최소로 드는 힘"을 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int n;
vector<int> order;
int cache[100005][5][5]; //[누를 순서][현재 왼발 위치][현재 오른발 위치] = 지금부터 끝까지 누르는데 최소 힘

void pre() {
	for (int i = 0; i < 100005; i++) {
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < 5; k++) {
				cache[i][j][k] = -1;
			}
		}
	}
}

int cost(int here, int there) {

	//중앙에서 다른 지점으로 이동할때
	if (here == 0) {
		return 2;
	}

	//반대편으로 이동할때
	else if (abs(here - there) == 2) {
		return 4;
	}

	//같은 지점을 누르는 경우일때
	else if (here == there) {
		return 1;
	}

	//다른지점에서 인접한 지점으로 이동할때
	return 3;
}

int solve(int index, int left, int right) {

	if (index == n) {
		return 0;
	}

	int& ret = cache[index][left][right];
	if (ret != -1) {
		return ret;
	}

	ret = 987654321;

	//왼발로 order[index]를 누를때
	//왼발로 누르면 오른발과 같은 위치가 안되는 경우
	if (order[index] != right) {
		ret = min(ret, cost(left, order[index]) + solve(index + 1, order[index], right));
	}

	//오른발로 order[index]를 누를때
	//오른발로 누르면 왼발과 같은 위치가 안되는 경우
	if (order[index] != left) {
		ret = min(ret, cost(right, order[index]) + solve(index + 1, left, order[index]));
	}

	return ret;
}


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

	pre();

	while (1) {
		int input;
		cin >> input;

		if (input == 0) {
			break;
		}

		order.push_back(input);
	}
	n = order.size();

	int result = solve(0, 0, 0);

	cout << result;

	return 0;
}