백준 1144번 - 싼 비용

싼 비용 (백준 1144번)

개념 : Connection Profile DP
난이도 :
링크 : https://www.acmicpc.net/problem/1144

---

근래 풀어봤던 문제 중 가장 신박한 동적 계획법 문제였다. 최근 m(열의 개수)개의 칸의 프로파일 정보를 담아 끝까지 연결 상태를 이어나간다. std::unordered_map을 이용해야만 다이나믹 프로그래밍은 처음이었던 것 같다. 어차피 본인도 자료를 보며 구현했기에, Connection Profile DP를 설명하기 보단 참고한 자료를 첨부한다.

jh05013님 블로그 : Connection Profile DP

최근 m(예시 : 6)개의 연결 상태가 [1, 0, 0, 2, 0, 1] 라면 직전 칸과 m번째 전 칸이 같은 연결요소에 속해있고, 3번째 전 칸은 다른 연결요소에 있음을 이야기한다. std::vector 자체를 hashing 하면 std::vector 자체로 std::unordered_map을 이용할 수 있었겠지만, 굳이 그러지 않고 저 배열을 그대로 10진수로 바꾸었다. 즉, 100201로 변환한 뒤, 이를 key로 std::unordered_map에 넣었다. 연결요소를 아무렇게나 관리하면 [1, 0, 0, 0, 0, 1] 이나 [2, 0, 0, 0, 0, 2] 의 의미가 완전이 같음에도 불구하고 여러개의 상태가 생겨버리기 때문에, 이를 정규화(?) 하는 것이 중요하다. std::unordered_set을 이용하면 쉽게 할 수 있다.

해당 상태를 관리하는 것이 너무 빡셌기 때문에, 비효율을 감안하더라도, semi OOP 느낌으로 객체로서 상태를 관리해주었다.

#include <bits/stdc++.h>

using namespace std;

int n,m;
int mat[81];
unordered_map<int, int> dp[81];

struct state
{
    vector<int> s;
    state() {
        s.resize(m);
    }
    state(int x) {
        s.resize(m);
        for (int i=0; i<m && x; ++i) {
            s[i] = x%10;
            x/=10;
        }
    }

    int val() {
        int ret = 0;
        for (int i=0, c=1; i<m; ++i, c*=10) {
            ret += s[i] * c;
        }
        return ret;
    }

    void norm() {
        unordered_map<int, int> ck;
        for (int i=0, t=1; i<m; ++i) {
            if (s[i] == 0) continue;
            if (ck.find(s[i]) == ck.end()) ck[s[i]] = t++;
            s[i] = ck[s[i]];
        }
    }

    bool alone() {
        unordered_set<int> t;
        for (int x : s) if (x) t.insert(x);
        return t.size() == 1;
    }

    bool up_alone() {
        int x = s.back();
        for (int i=0; i<m-1; ++i) if (s[i] == x) return false;
        return true;
    }

    state prop(int j, bool chk) {
        state ret;
        for (int i=1; i<m; ++i) ret.s[i] = s[i-1];
        if (chk) {
            int u = s.back();
            int l = j? s[0] : 0;
            if (u) {
                ret.s[0] = u;
                if (l) for (int i=1; i<m; ++i) if (ret.s[i] == l) ret.s[i] = u;
            } else if (l) {
                ret.s[0] = l;
            } else {
                ret.s[0] = 1234;
            }
        } 
        ret.norm();
        return ret;
    }
};



int main()
{
    cin >> n >> m;
    for (int i=0; i<n*m; ++i) cin >> mat[i];
    dp[0][0] = 0;
    dp[0][1] = mat[0];
    int ans = min(0, mat[0]);
    for (int i=1; i<n*m; ++i) {
        for (auto [k, v] : dp[i-1]) {
            state st(k);
            int up = st.s.back();
            state prop = st.prop(i%m, 1);
            int val = prop.val();
            if (dp[i].find(val) == dp[i].end()) dp[i][val] = v + mat[i];
            else dp[i][val] = min(dp[i][val], v + mat[i]);
            if (prop.alone()) {
                ans = min(ans, dp[i][val]);
            } 
            if (!st.s[m-1] || !st.up_alone()) {
                prop = st.prop(i%m, 0);
                val = prop.val();
                if (dp[i].find(val) == dp[i].end()) dp[i][val] = v;
                else dp[i][val] = min(dp[i][val], v);
            }
        }
    }
    cout << ans;
} // namespace std;