[Algorithm]Baekjoon 2342번 : Dance Dance Revolution

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

2342번: Dance Dance Revolution

 
using namespace std;
 
 
int dp[100001][5][5] = { 0 };
int movingCost[5][5] =
{
    {-10000, 2, 2, 2, 2},
    {-10000, 1, 3, 4, 3 },
    {-10000, 3, 1, 3, 4 },
    {-10000, 4, 3, 1, 3 },
    {-10000, 3, 4, 3, 1 }
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int index = 1;
    int target = 0;
    memset(dp, 0x3f, sizeof(dp));
 
    dp[0][0][0] = 0; // 시작지점 초기화.
 
    while (1)
    {
        cin >> target;
        if (target == 0) break;
 
        for (int left = 0; left < 5; ++left)
        {
            for (int right = 0; right < 5; ++right)
            {
                if (dp[index-1][left][right] == 0x3f3f3f3f) continue;
 
                int leftToTarget = movingCost[left][target];
                int rightToTarget = movingCost[right][target];
 
                dp[index][left][target] = min(dp[index][left][target], dp[index-1][left][right] + rightToTarget);
                dp[index][target][right] = min(dp[index][target][right], dp[index - 1][left][right] + leftToTarget);
            }
        }
 
        ++index;
    }
    
    int answer = 0x3f3f3f3f;
 
    for (int i = 0; i < 5; ++i)
    {
        for (int j = 0; j < 5; ++j)
        {
            answer = min(answer, dp[index - 1][i][j]);
        }
    }
 
    cout << answer;
}
 
 
 
 

 

또 한번 실력향상 할 수 있었던 문제..

재귀로도풀어보고 나름 점화식 세워서 하려다가 안풀려서 다른 풀이를 참고했다.

이런식의 바텀업방식의 DP풀이도 반드시 익혀야하는 것 같다.

 

각각 인덱스 0~5를 진행하는 이중반복문은(32번째 라인), 이전차례때 도착되어진 경우의 수들을 먼저 찾는 것이다.

36번째 라인을 보면 dp[index-1][left][right] == 0x3f3f3f3f 이면 그냥 지나쳐버리는 것을 알 수 있는데, 만약 dp[3][1][4] == 0x3f3f3f3f 라면 3번째 때 [1][4]에 도착한 경우의 수는 존재하지 않는다는 것이다.

 

이렇게 일단 이전에 도착한 경우의수들을 전부 순회하면서 찾은 후, 현재 옮겨야 할 숫자인 target을 왼발,오른발로 이동한 값을 dp테이블에 갱신해주면 된다.

 

예시를 들자면 dp[3][1][2]가 0x3f3f3f3f가 아닌, 즉 이전에 도착한 경우의 수가 존재한다고 가정하자.

이상태에서 target이 3이라고 치면 왼발을 3으로 옮길경우 dp[4][3][2]를 업데이트하면 되고 오른발을 3으로 옮길경우 dp[4][1][3]을 업데이트 해주면 된다.

위 코드처럼 갱신하는 이유는, dp[4][3][2]값의 경우 여러곳에서 접근할 수 있다는 것이다.

 

즉, 방금 말했다시피 dp[3][1][2]에서 target이 3이라서 왼쪽발로 3을밟을경우에도 dp[4][3][2]값에 접근을 하게된다.

혹은 dp[3][4][2]라는 경우의수가 존재하는 경우에도 target이 3이면, 왼쪽발로 3을 밟아버리면 dp[4][3][2]에 접근하게된다.

즉 특정차례의 [left][right] 에 접근하는 경우의 수는 여러가지라는 것이다.

[2][4] -> [1][4]도 되고

[3][4] -> [1][4]도 되며

[1][4] -> [1][4]도 된다. 이 많은 경로들중에서 최종적으로 [현재차례][1][4]의 최솟값을 구해야 하니, 위와 같이 갱신하게된다.

 

그리고 개수많은거 아니면 이런문제는 코스트비용같은건 그냥 룩업테이블로 만드는게 시간도 빠르고 더 직관적으로 코드작성이 가능하다.

규칙이 있기 때문에 계산해서 구하는것도 가능하긴 한데, 굳이..?