백준 - Dance Dance Revolution (2342번)

2342번: Dance Dance Revolution

승환이가 지시에 따라 두 발을 딛을 때, 드는 최소의 힘 을 구하는 문제 입니다. 발은 두개이고, 발판은 5개 밖에 안되니 마치 비용이 상대적으로 적은 발로 발판은 딛는 방법을 생각할수 있으나 이는, 4+1+1+1 비용이 들 것을 1+3+3+3 으로 들어 오히려 더 힘들게 게임을 끝내는 경우가 있기 떼문에 그리디로는 풀 수 없습니다.

 

그렇다면 하나의 발판을 두 발 중 하나가 딛는 경우로 BFS 방법 밖에 없는데, 그렇다고 해서 아무 생각 없이 BFS를 돌리면 100000번째 발판이 들어올 때, 경우의 수는 2^100000 이 되므로 당연히 TLE가 발생합니다.

 

이런 무지막지한 경우의 수를 막아야 합니다. 즉, 경우의 수를 줄여야 하는데 가장 쉬운 방법은 중복된 부분은 지우는 방법 입니다.

 

발은 두개, 발판은 다섯개 입니다. 그러면 총 경우의 수는 25가지, 그 이상을 벗어날 수 없습니다. 즉, 반복문을 계속 돌려서 경우의 수 중에 (2,1), (3, 1)이 나오고 input 값으로 2가 들어온 다면, (2,1) -> (2,1)로 같은 발판을 밟을 수 있고 (3,1) ->(2,1)로 왼쪽 발을 옮길 수도 있습니다. 결국 (2,1), (3,1) 둘 다 (2,1)로 들어갈 수 있고, 중복된 위치이기 때문에 둘 중 하나를 지우면 됩니다. 이때 구하라는 것은 최솟값이므로 (2,1) ->(2,1) 비용과 (3,1)->(2,1) 가는 비용중 가장 비용이 적은 값을 저장하는 다이나믹 프로그래밍을 활용하면 됩니다.

 

코드(C)

#include <stdio.h>
#include <stdlib.h>
#define INF 1e9

int get_c(int x, int y)
{
	// x -> y로 이동할때 드는 비용 계산
	if(x == 0) return 2;
	if(x == y) return 1;
	if(abs(x-y) == 2) return 4;
	return 3;
}

int main(void)
{
	int x, ans = INF, dp[2][5][5];
	register int i, j, k;


	// 1e9로 dp 배열 초기화
	for(k = 0; k < 2; k++)
		for(i = 0; i < 5; i++)
			for(j = 0; j < 5; j++)
				dp[k][i][j]=INF;
	k=0;
	dp[0][0][0]=0;
	while(1)
	{
		// 입력
		scanf("%d", &x);
		if(!x) break;
		int m = k % 2;
		for(i = 0; i < 5; i++)
		{
			for(j = 0; j < 5; j++)
			{
				int v;
				if(dp[m][i][j] == INF) continue;
				// 왼발
				if(x != j)
				{
					// 비용
					v = get_c(i, x) + dp[m][i][j];
					if(v < dp[(m+1)%2][x][j])
						dp[(m+1)%2][x][j] = v;
				}
				// 오른발
				if(x != i)
				{
					// 비용
					v = get_c(j, x) + dp[m][i][j];
					if(v < dp[(m+1)%2][i][x])
						dp[(m+1)%2][i][x] = v;
				}
				// 발판이 발에서 떨어짐
				dp[m][i][j] = INF;
			}
		}
		k++;
	}
	for(i = 0; i < 5; i++)
		for(j = 0; j < 5; j++)
			if(dp[k%2][i][j] < ans) ans = dp[k%2][i][j];

	printf("%d\n", ans);
	return 0;
}