[백준 c++] 2342 Dance Dance Revolution

문제

https://www.acmicpc.net/problem/2342
처음엔 두 발 모두 중점이다. 시작 후엔 두 발을 같은 곳에 둘 수 없다.

발을 옮길 때 드는 힘은 출발지와 목적지에 따라 다르다.
제자리: 1
중점 -> 다른 곳: 2
중점아닌 곳 -> 인접한 곳: 3
중점아닌 곳 -> 반대편: 4

이때, 지시사항을 만족하도록 하는 최소한의 힘을 구하는 문제다.

풀이

시행착오 🤕

모든 경우의 수를 탐색해야하기 때문에 DP를 사용했다.
처음 풀었을 때는 dp[오른발][왼발][사용한 힘]으로 두고 풀었다.
왜 이렇게 풀었냐면 오른발, 왼발 위치만 가지고 특정 상태값을 메모이제이션하고 싶은데 위치 같은거는 나중에도 중복될 수 있으니까 사용한 힘을 추가로 dp에 저장하고 꺼내쓰면 될거라고 생각했기 때문이다.dp[오른발][왼발][사용한 힘] = 사용한 힘 이렇게 저장했다. 아무튼 이런식으로 풀어서 질문게시판에 있는 모든 반례까지 다 통과했지만 결국 제출하자마자 틀렸다고 떴다👺 나는 정들었던 내 코드를 다시 고쳐보려고 했는데 결국 잘 안됐고, dp 설정부터 잘못한거같다는 생각이 들어서 결국 다시 처음부터 풀었다.

---

dp[오른발][왼발][타겟 인덱스] = 사용한 힘로 두면 된다.
(왜 입력 인덱스를 사용할 생각을 못했을까👹)
앞으로는 dp 레벨 구분할 때 인덱스를 적극 활용할 것.

왼발 이동 OR 오른발 이동으로 경우의 수가 나뉘기 때문에 위와 같이 그래프를 그릴 수 있다. 둘 중 최소값으로 dp값을 저장하면 된다.
그리고 이동할 때마다 드는 힘은 따로 함수를 정의해서 구하면 편하다.

int check(int from, int to)
{
    if (from == 0)
        return 2;
    if (from == to)
        return 1;
    if (abs(from - to) == 2)
        return 4;
    return 3;
}

출발하는 위치를 from, 옮길 위치를 to라고 정의한다. 그리고 문제에서 주어진 경우에 따라 return 값을 주면된다 🤩

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
int t, dp[5][5][100001];
vector<int> v;
int check(int from, int to)
{
    if (from == 0)
        return 2;
    if (from == to)
        return 1;
    if (abs(from - to) == 2)
        return 4;
    return 3;
}
int solve(int y, int x, int target)
{
    if (target == v.size())
        return 0;
    if (dp[y][x][target] != -1)
        return dp[y][x][target];

    int left = solve(v[target], x, target + 1) + check(y, v[target]);
    int right = solve(y, v[target], target + 1) + check(x, v[target]);

    return dp[y][x][target] = min(left, right);
}

int main()
{
    while (1)
    {
        cin >> t;
        if (!t)
            break;
        else
            v.push_back(t);
    }
    memset(dp, -1, sizeof(dp));
    cout << solve(0, 0, 0) << "\n";
}