(BOJ12869 - 뮤탈리스크) k진수 memo

각 SCV의 체력 ≤ 60

최대 3개의 SCV

≫ 3자리 61진수 수로 인코딩 가능

 

인코딩/디코딩에 사용된 base conversion 코드

// decimal num to base num
vi decToBase(int num, int base) {
    vi res;
    while (num) {
        res.push_back(num % base);
        num /= base;
    }
    reverse(all(res));
    return res;
}

// base num to decimal num (key)
int baseToDec(vi baseNum, int base) {
    int res = 0, N = baseNum.size();
    for (int i = 0; i < N; i++) {
        res *= base;
        res += baseNum[i];
    }
    return res;
}

 

K진수 memo 코드 (★ 친 부분)

const int BASE = 61; // ★ 61진수
int memo[226981];
vector<vi> subComb = { {1,3,9}, {1,9,3}, {3,1,9}, {3,9,1}, {9,1,3}, {9,3,1} };

auto DEC = [](int a, int b) {return a > b;};

// 현재 HP 상태 (key)가 주어질 때, 남은 최소 공격 횟수 반환 (Optimal substructure)
int dp(int key) {
    if (key == 0)
        return 0;

    if (memo[key]) return memo[key];
    int& ret = memo[key];

    ret = INF;
    vi hp = decToBase(key, BASE); // ★ Decoding

    // BF - 모든 경우의 수 탐색
    for (vi& sub : subComb) {
        vi tmpHP = hp;
        FOR(i, 0, 3) {
            tmpHP[i] -= sub[i];
            if (tmpHP[i] < 0) tmpHP[i] = 0; // clipping to 0
        }

        sort(all(tmpHP), DEC); // ★ Invariant - 인코딩 전 내림차순 정렬
        int nxtKey = baseToDec(tmpHP, BASE); // ★ Encoding
        ret = min(ret, 1 + dp(nxtKey));
    }

    return ret;
}

 

 

---

사실 체력이 60이하로 작기 때문에, 무지성으로 N개의 자릿수별로 숫자를 따로따로 memo해도 된다 (N차원 DP)

int cache[61][61][61];
int dp(int a, int b, int c)
{
    if (a <= 0 && b <= 0 && c <= 0)
        return 0;
    if (a < 0) a = 0; if (b < 0) b = 0; if (c < 0) c = 0;
    if (cache[a][b][c] > 0)
        return cache[a][b][c];

    int& ret = cache[a][b][c];
    ret = numeric_limits<int>::max() - 1;
    ret = min(ret, dp(a - 9, b - 3, c - 1));
    ret = min(ret, dp(a - 9, b - 1, c - 3));
    ret = min(ret, dp(a - 3, b - 9, c - 1));
    ret = min(ret, dp(a - 3, b - 1, c - 9));
    ret = min(ret, dp(a - 1, b - 9, c - 3));
    ret = min(ret, dp(a - 1, b - 3, c - 9));
    return ++ret;
}