백준 2342번 Dance Dance Revolution

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

2342번: Dance Dance Revolution

 

풀이

먼저 DP배열을 정의합니다. 

 

DP[i번째발판을 누를차례][왼발위치][오른발위치] //i번째까지 도달하는데 사용한 최소힘

 

처음에는  상태가 이렇습니다.

 

0번차례(시작하지 않은상태)에 왼발 오른발 모두 0번 발판에 있습니다.

DP[0][0][0]으로 표현가능합니다.

 

예제 입력을 확인하면 1번 차례에 1번 발판을 밟으라고 나와있습니다.

1 2 2 4 0

 

 

두개의 상황이 나올 수 있겠네요.

왼발을 1번으로 옮겼을 경우 오른발을 1번으로 옮겼을경우

 

 

예제를 다시 확인해보면 2번 차례에 2번 발판을 밟으라고 나와있습니다.

 

다음과 같이 상황이 나올 수 있어요.

해당 그림을 통해서 점화식이 유추해보면 다음과 같습니다.

 

 

Arr : i번째에 밟아야되는 발판 DP : i번째까지 밟을때의 최소 힘 lc : 왼발로 다음발판을 밟았을때 드는힘(코드참고) l : 왼발의 위치 rc : 오른발로 다음발판을 밟았을때 드는힘(코드참고) r : 오른발의 위치

DP[i][l][r] =min(DP[i+1][Arr[i+1]][r] + lc, DP[i+1][l][Arr[i+1]] + rc);

 

하지만 주의 해야할게 있어요!!

 

 

해당 사항을 고려해서 점화식을 수정하면..

 

Arr : i번째에 밟아야되는 발판 DP : i번째까지 밟을때의 최소 힘 D : 메모이제이션을 하기 위해 선언된 함수(코드참고) lc : 왼발로다음발판을 밟았을때 드는힘(코드참고) l : 왼발의 위치 rc : 오른발로 다음 발판을 밟았을때 드는힘(코드참고) r : 오른발의 위치

if(Arr[i + 1] != r)          DP[i][l][r] = min(DP[i][l][r], D(i + 1, Arr[i + 1], r) + lc ); if(Arr[i + 1] != l)          DP[i][l][r] = min(DP[i][l][r], D(i + 1, l, Arr[i + 1]) + rc );

 

코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

const int INF = 0x3f3f3f3f3f3f3f3fLL;

int N = 1;
int Arr[100002];
int DP[100002][5][5]; //i번째까지 도달하는데 사용한 최소힘
int Cost[5][5] = {
	{1,2,2,2,2},
	{2,1,3,4,3},
	{2,3,1,3,4},
	{2,4,3,1,3},
	{2,3,4,3,1}
};

int D(int i, int l, int r)
{
	if (i >= N)
		return 0;
	if (DP[i][l][r] != INF)
		return DP[i][l][r];
	int rc = Cost[r][Arr[i + 1]] * (i + 1 < N);
	int lc = Cost[l][Arr[i + 1]] * (i + 1 < N);
	if (Arr[i + 1] != r)
		DP[i][l][r] = min(DP[i][l][r], D(i + 1, Arr[i + 1], r) + lc);
	if (Arr[i + 1] != l)
		DP[i][l][r] = min(DP[i][l][r], D(i + 1, l, Arr[i + 1]) + rc);
	return DP[i][l][r];
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	memset(DP, INF, sizeof(DP));

	while (true)
	{
		int a;
		cin >> a;
		if (a == 0)
			break;
		Arr[N++] = a;
	}

	cout << D(0, 0, 0) << endl;
}

 

-----------------------------------------------------------------------------------------------------------------------------------

질문은 언제나 환영합니다.