백준 - 2342 Dance Dance Revolution

 

해결과정 - DP

처음에는 특정한 규칙이 있을거라 생각하여 사이클을 찾아보거나, 어떨때 최적이 될까를 찾아 보았다 하지만 딱히 규칙이 보이지 않아 고민하던중 한번씩 확인해 나가면 4 * 4 * 10만 번만 탐색하면 된다는 것을 알아차렸다.

 

일반적으로 탐색을 하게 되면 이미 확인했던 공간도 확인하게 되어 많은 시간이 소요되게 된다 따라서 바텀 업 방식이 아닌 탑 다운 방식을 도입하고 메모제이션을 사용하여 이미 방문한 곳은 방문하지 않도록 해주었다.

 

#include <bits/stdc++.h>

#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;

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

vector<int> v;
int dp[5][5][100001];

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) + calc_cost(y, v[target]);
    int right = solve(y, v[target], target + 1) + calc_cost(x, v[target]);

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

int main() {
    FAST;
    int n;

    memset(dp, -1, sizeof(dp));
    while (cin >> n) {
        if (n == 0) break;
        v.push_back(n);
    }
   
    cout << solve(0, 0, 0);

    return 0;
}

 

후기

이젠 귀찮아서 하나의 헤더파일에 필요해 보이는 함수들을 때려넣어서 include를 하나만 선언해도 되게하였다 편하다 ㅎㅎ

 

아 넥슨 들어가고 싶다.