boj, 백준) 2342. Dance Dance Revolution ( C / C++)

1. 문제 링크

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

2342번: Dance Dance Revolution

2. 문제 설명

DDR 게임을 하면서 발을 움직일 건데 가장 적은 에너지를 사용하여 움직일 때, 에너지의 최솟값을 찾자.

 

움직일 때 에너지 값은, 열에서 행으로 이동한다고 가정했을 때,

열 -> 행	0	1	2	3	4
0	1	2	2	2	2
1	0	1	3	4	3
2	0	3	1	3	4
3	0	4	3	1	3
4	0	3	4	3	1

이다.

 

 

3. 문제 힌트

 

결국엔 모두 다 탐색해야 한다. 그런데 DP를 사용해서 빨리 찾아야 한다.

dp[단계][left][right]로 정의하고, left, right는 해당 단계에서 발의 위치를 나타낸다고 하자.

 

그럼 현재 단계에서 다음 단계로 넘어갈 때 어떻게 해야 할까?

 

 

4. 문제 풀이

우선 문제에 나오는 조건들이 중요하다. 

 

두 발이 0인 경우를 제외하고 같으면 안 된다.

이조건은 현재 단계에서 다음 단계로 넘어갈 때 if문을 사용해서 처리해줄 수 있지만 그럼 복잡해지니 그냥 같은 번호일 때 INF를 반환하도록 하자. 여기서 INF는 정답에 영향을 주지 않는 충분히 큰 수이다.

 

그럼 다음 단계로 넘어갈 때 값이 어떻게 될까.

현재 단계에서 다음 단계로 넘어갈 때는 2가지 경우가 있다. 왼발을 움직일 것이냐 오른발을 움직일 것이냐. 그 두 개 중 최솟값을 취할 것이다.

 

즉,

dp(현재, left, right) = 

min ( dp(현재 + 1, 다음 발판, right) + weight[left][다음 발판]  , dp(현재 + 1, left, 다음 발판) + weight[right][다음 발판] )이 되겠다.

 

메모이제이션 하는 것을 잊지 말고 구현해주도록 하자.

 

즉, 결국엔 완전 탐색이다. 그런데 DP를 사용해서 시간을 줄인다는 점 명심하자.

 

5. 코드

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

//[a][b] : move a to b
int s[5][5];
int step[100001];
int len = 1;
const int INF = 987654321;

int dp_table[100001][5][5];

int dp(int cur, int l, int r) 
{
	if (cur == len - 1) return 0;
	if ((l !=0 && r != 0) && l == r)	return INF;

	//memoization
	int &cache = dp_table[cur][l][r];
	if (cache != -1)return cache;

	return cache = min(dp(cur + 1, step[cur + 1], r) + s[l][step[cur + 1]],
		dp(cur + 1, l, step[cur + 1]) + s[r][step[cur + 1]]);
}
int main()
{
	scanf("%d", &step[len++]);

	while (step[len - 1] != 0) 
		scanf("%d", &step[len++]);
	
	memset(dp_table, -1, sizeof(dp_table));

	//score
	for (int i = 0; i <= 4; ++i) 
		s[i][i] = 1;
	for (int i = 1; i <= 4; ++i) {
		s[0][i] = 2;
	}
	s[1][2] = s[1][4] = s[2][1] = s[2][3] = s[3][2] = s[3][4] = s[4][3] = s[4][1] = 3;
	s[1][3] = s[2][4] = s[3][1] = s[4][2] = 4;

	//solve
	printf("%d", dp(0, 0, 0));

	return 0;
}

6. 결과

 

지적, 댓글 언제나 환영입니다!!