이전에 풀었던 RGB 거리와 유사한 방식으로 풀었다.

최적의 값 dp[t]를 dp[t-1]을 통해서 구할 수 있으려면

t일 때의 최솟값 dp[t] 뿐만 아니라 왼발과 오른발의 위치 또한 계산에 포함되어야 하므로,

(dp[t-1]의 최솟값을 만족했던 왼발과 오른발의 위치가 dp[t]의 시점에서는 t-1의 해당 위치가 최적이 아닐 수 있기 때문)

t일 때의 왼발과 오른발의 모든 조합에서의 최솟값 dp[t]를 별도로 계산을 해야 한다.

편의를 위해 unordered_map을 사용했지만, 얼마든지 더 단순한 컨테이너를 사용할 수도 있을 것이다. 

공유할 정도로 이쁜 코드는 아니지만, 기록의 목적으로 남겨본다.

먼저 현재 발의 위치에서 옮기려는 위치 까지의 비용을 계산해주는 함수를 작성했다.

enum FootPos {
	CENTER = 0,
	UP,
	LEFT,
	DOWN,
	RIGHT
};

int calcEnergy(const int& target, FootPos prev_position) {
	FootPos target_position = (FootPos)target;

	if (target_position == prev_position) return 1;
	else if (prev_position == FootPos::CENTER)
		return 2;
	else if ((prev_position == FootPos::LEFT && target_position == FootPos::RIGHT) ||
		(prev_position == FootPos::RIGHT && target_position == FootPos::LEFT) ||
		(prev_position == FootPos::UP && target_position == FootPos::DOWN) ||
		(prev_position == FootPos::DOWN && target_position == FootPos::UP))
		return 4;
	else
		return 3;
}

후에 dp[0]에서의 최적값은 왼발 혹은 오른발을 order[0]의 위치로 옮긴 경우가 유일하므로 수동으로 값을 대입해주고,

dp[1] 이후의 값은 dp[0]일때와 유사하게

dp[t-1]에 존재하는 왼발과 오른발의 조합에서 왼발을 기존 위치에서 order[t]의 위치로 옮길 때

calcEnergy가 최소가 되는 값을 구해서 dp[t]의 값을 갱신해주는 방법으로 구현했다.

vector<unordered_map <int, int >> dp(order.size());
dp[0][order[0] * 5] = calcEnergy(order[0], FootPos::CENTER);
dp[0][order[0]] = calcEnergy(order[0], FootPos::CENTER);
for (int t = 1; t < order.size(); t++) {
    int min = -1;
    auto LEFT = (FootPos)(order[t]);
    for (int footpos = 0; footpos < 5; footpos++) {
        auto RIGHT = (FootPos)footpos;
        if (LEFT == RIGHT) continue;

        int min = -1;
        for (int prevpos = 0; prevpos < 5; prevpos++) {
            auto prevLEFT = (FootPos)prevpos;
            if (dp[t - 1].count(prevLEFT * 5 + RIGHT) == 0) continue;
            auto cost = dp[t - 1][prevLEFT * 5 + RIGHT] + calcEnergy(LEFT, prevLEFT);
            if (min == -1 || min > cost)
                min = cost;
        }
        if (min != -1)
            dp[t][LEFT * 5 + RIGHT] = min;
    }

    auto RIGHT = (FootPos)(order[t]);
    for (int footpos = 0; footpos < 5; footpos++) {
        auto LEFT = (FootPos)footpos;
        if (LEFT == RIGHT) continue;

        int min = -1;
        for (int prevpos = 0; prevpos < 5; prevpos++) {
            auto prevRIGHT = (FootPos)prevpos;
            if (dp[t - 1].count(LEFT * 5 + prevRIGHT) == 0) continue;
            auto cost = dp[t - 1][LEFT * 5 + prevRIGHT] + calcEnergy(RIGHT, prevRIGHT);
            if (min == -1 || min > cost)
                min = cost;
        }
        if (min != -1)
            dp[t][LEFT * 5 + RIGHT] = min;
    }
}

이번에도 집중의 문제로 구현이 까다로워서 시간이 조금 걸렸다.

비교적 간단한 문제였는데 빨리 풀지 못해서 아쉬웠다.