[ 백준 / 2342 ] Dance Dance Revolution (C++)

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

 

난이도 : 골드 3 
알고리즘 유형 : DP 
풀이 시간 : 51분 

문제 풀이 

DDR의 입력이 지시 사항으로 주어질 때, 승환이가 사용하는 최소 힘을 출력하라. DDR을 하는 데 사용되는 힘은 다음과 같다.

중앙 -> 다른 지점 : 2
인접 지점 (왼쪽 -> 위 / 아래) : 3
반대편 (왼쪽 -> 오른쪽) : 4

 

해당 문제를 마주하면 그리디로 문제를 해결해야 할 지, DP로 문제를 해결해야 할 지 머리가 매우 뜨거워진다. 

이럴 땐, 각 알고리즘의 정의를 다시 한 번 떠올리자.

그리디 알고리즘의 경우, 항상 최적의 값을 갖는 경우로만 이동하고자 하는 알고리즘이다.

DP의 경우, 이전 결과가 현재 결과에 영향을 미치지 않고, 단순히 이전 결과를 사용할 때 활용할 수 있는 알고리즘이다.

 

여기서 키 포인트는 해당 문제는 항상 최적의 값을 보장하기 어렵다는 점이다. 예제에 대해서 가능한 경우를 전개해 보면 이 이유를 쉽게 찾을 수 있다.

따라서 해당 문제는 DP로 풀어나갈 수 있다.

 

DP에는 2가지 방법이 있는데, 재귀 함수를 활용한 `top-down`이 있고, 일반적으로 모든 배열을 탐색하는 `bottom-up` 방식이 있다. 주인장은 `top-down` 방법을 활용하여 문제를 풀이했다.

 

먼저 해당 문제는 왼발을 이동할 것인지 vs 오른발을 이동할 것인지 에 대한 두 가지 경우가 존재한다. 

따라서 DFS와 같은 방법으로 마지막 수열의 경우까지 가 본 뒤, 해당 위치를 시작으로 이동한 힘을 더해가는 방식을 사용할 것이다. 이 방법이 top-down이다. 위에서부터 다시 아래로 내려가면서 값을 구하기 !

 

이 때, 분명히 중복되는 경우가 존재할 것이다. 이 경우에는 "메모이제이션" 즉, DP 배열에 저장된 값을 활용하여 수열의 모든 경우를 탐색하지 않도록 가지치기를 진행해주어야 한다. 이를 위해서는 현재 DP 배열의 값이 최솟값임을 보장해야 한다.

 

최솟값을 보장하기 위해서는 왼발 이동 결과와 오른발 이동 결과를 비교해서 현재 DP 배열에 두 값 중 작은 값을 저장하면 된다. 이를 통해 최소 경우를 보장할 수 있다.

 

시간복잡도는 $O(2^{수열길이})$가 걸리지만, DP로 인해 최적화를 진행해주어 충분히 시간 내에 실행할 수 있다.

 

코드

/*
중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4

두 발이 동시에 움직이지 않는다 & 두 발이 같은 지점에 있는 것이 허락되지 않는다.

중앙 -> 다른 지점 : 2
인접 지점 (왼쪽 -> 위 / 아래) : 3
반대편 (왼쪽 -> 오른쪽) : 4

최소 힘을 출력하자

풀이 : 2차원 dp를 사용한다 ? (어떤 발을 움직였냐에 따라서 배열에 다르게 저장하기)
bottom-up 사용 가능 ? x, top-down이 더 쉽다.
	-> 발 바뀌는 경우에 동일하기 때문임
고려사항 : 현재 발이 어디에 있는지 어떤 발을 움직이는지에 따라서 달라진다.

*/

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n;
int arr[100002] = { 0, };
int dp[100002][5][5];
int idx = 0;

int getVal(int l, int r) {
	if (l == r)
		return 1;
	else if (!l)
		return 2;
	else if (abs(l - r) % 2)
		return 3;
	return 4;
}

int DDR(int depth, int left, int right) {
	if (depth == idx) 
		return 0;	// top-down은 내려가면서 값을 더해주기 때문에 초기값을 도착지에서 0으로 잡는다.
	if (dp[depth][left][right] != -1)
		return dp[depth][left][right];

	// 왼쪽으로 간 경우와 오른쪽으로 간 경우의 값을 비교하여 더해주며 내려가자
	int nleft = DDR(depth + 1, arr[depth], right) + getVal(left, arr[depth]);
	int nright = DDR(depth + 1, left, arr[depth]) + getVal(right, arr[depth]);

	dp[depth][left][right] = min(nleft, nright);
	
	return dp[depth][left][right];
}

int main() {
	
	while (1) {
		cin >> n;
		if (!n)
			break;
		arr[idx++] = n;
	}

	memset(dp, -1, sizeof(dp));
	cout << DDR(0, 0, 0) << '\n';
	return 0;
}

배운 점

해당 문제를 봤을 때 그리디로 접근해야 하는지, DP로 접근해야 하는지에 대해 시간을 많이 투자하였다. 만약 코딩테스트였다면 시간이 부족했을 수도 있을 것 같다. 이를 방지하기 위해 그리디 vs DP를 사용하는 조건을 항상 머릿속에 깨닫고 있어야겠다.

또한, top-down 방식으로 최솟값을 구하는 방법은 처음 사용했기에 생소했다. 하지만 결국 bottom-up과 같은 방식으로 값을 업데이트 해주기 때문에 금방 익숙하게 사용할 수 있을 것으로 생각한다.