문제

DDR 머신에서 두발의 이동경로의 최소 비용을 구하는 문제.

매 선택마다. 2개의 선택지가 있다. 왼발 또는 오른발을 사용해서 타일을 눌러야한다. 물론 그리디는 아니다. 지금의 비용이 조금 드는 선택을 했더라도 다음선택에서 많이 들수 있다. 그렇다고 모든 경우의 수를 비교하기엔 시간복잡도가 2^n이다. 그러면 DP로 중복되는걸 줄이면서 해보면 좋겠다.

부분문제를 찾자.

부분문제로 나눌 수 있을까 라는 의문이 들었다. 입력을 자르는것은 허용되지 않는다. 1 2 2 4 를 방문한다는게 2 다음에 4를 누른다는 정보만 포함하는 것은 아니다.1 2 2까지 했을 때 왼발 오른발의 상태가 중요하다. 어떡하지.

완전탐색에서 힌트를 얻다.

만약 매 선택마다 왼발로 갈지 오른발로 갈지 선택할 수 있다고 했을 때, 각 입력마다 선택지는 2배로 늘어난다. 하지만 그 모든 선택지가 다 의미 있나? 결국은 양발이 갈 수 있는 도착지는 25가지 조합 중 한가지일 것이고, 각각의 선택지는 비용만 다를 것이다. 그렇다면 최소비용인것만이 다음 단계로 넘어갈때 의미가 있다. DP[i][L][R] = i단계에서 각 발이 LR일때, 현재 타일까지 밟은비용의 최솟값.

Untitled

정리하자면 2^n 으로 불어나는 가짓수를 중복되는 스텝에 대해서 최솟값만을 저장해서 25가지로 줄인다.

예를 들어 4, 0에서 1,0 으로 가는과 2,0 에서 1, 0으로 가는것은 1,0 으로 간 이상 더 이상 서로 다른것이라고 하기 어렵다. 그렇다면 두가지중 비용이 작은 것만을 골라 저장하고, 아닌것은 더이상 보지 않는 가지로 쳐버리면 된다.

code

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <math.h>
#include <algorithm>
#define INF 50000000
using namespace std;

int validMin(int a, int b){
    if(a == -1) return b;
    if(b == -1) return a;
    return min(a,b);
}

int main() {
    int n=0,k,ans= INF;
    int dis[5][5];
    for(int l= 0 ; l < 5 ; l++){
        for(int r= 0 ; r < 5 ; r++){
            if( l == r) dis[l][r] = 1;
            else if(l == 0 || r == 0 )dis[l][r] = 2;
            else if(abs(l-r) == 2) dis[l][r] = 4;
            else dis[l][r] = 3;
        }
    }
    vector<int> goal;
    goal.push_back(-1);
    while(true){
        cin >> k;
        if( k == 0) break;
        goal.push_back(k);
        n++;
    }
    int dp[1000001][5][5];
    memset(dp, -1, sizeof(dp));
    dp[0][0][0] = 0;
    for(int i = 0; i< n; i++){
        for(int l= 0 ; l < 5 ; l++){
            for(int r= 0 ; r < 5 ; r++){
                int last = dp[i][l][r];
                if(last == -1 )continue;
                int& left = dp[i+1][l][goal[i+1]];
                int& right = dp[i+1][goal[i+1]][r];
                left = validMin(last + dis[r][goal[i+1]] ,left); 
                right = validMin(last + dis[l][goal[i+1]] , right);
            }
        }
    } 

    for(int l= 0 ; l < 5 ; l++){
        for(int r= 0 ; r < 5 ; r++){
            ans = validMin(ans , dp[n][l][r]);
        }
    }
    cout << ans;
                
            
    return 0;
}