[백준] 2342 - Dance Dance Revolution

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

2342번: Dance Dance Revolution

 

현재 발의 위치와 이동할 발의 위치에 따라 사용되는 힘이 달라지고,

주어진 수열에 적절히 발을 움직여 사용하는 최소 힘을 구하는 문제이다.

 

왼발, 오른발이 있으므로 모든 경우의 수를 따져보면 2^N, TLE가 날 것이다.

그리디도 생각을 했지만, 반례가 바로 떠올랐고 따라서 dp로 해결하였다.

 

dp[i][j][k] = i번째 행동을 j, k 위치의 발로 눌렀을 때 최소의 힘이라 정의하였다.

그러고 top-down 방식으로 진행하였다.

 

정말 단순하게 왼발을 움직였을 때와 오른발을 움직였을 때를 구분하여 최솟값으로 dp배열을 갱신하면 된다.

 

왼발을 움직였을 때 => go(n + 1, a[n], j) + getStrength(i, a[n])

오른발을 움직였을 때 => go(n + 1, i, a[n]) + getStrength(i, a[n])

 

#include <iostream>
using namespace std;

int a[100000], dp[100000][5][5], idx; //i번째 수열을 j, k 위치의 발로 눌렀을 때 최소 힘

int getStrength(int i, int j) {
	if (i == j) return 1;
	if ((i == 1 && j == 3) || (i == 2 && j == 4) || (i == 3 && j == 1) || (i == 4 && j == 2)) return 4;
	if (i == 0 || j == 0) return 2;
	return 3;
}

int go(int n, int i, int j) {

	if (idx == n) return 0;

	if (dp[n][i][j])return dp[n][i][j];

	int ret = min(go(n + 1, i, a[n]) + getStrength(j, a[n]), go(n + 1, a[n], j) + getStrength(i, a[n]));

	return dp[n][i][j] = ret;
}

int main() {

	while (1) {
		int n;
		cin >> n;
		if (n == 0)break;
		a[idx++] = n;
	}

	cout << go(0, 0, 0);

	return 0;
}