Algorithm in A..Z - 백준 2449 전구

www.acmicpc.net/problem/2449

2449번: 전구

---

접근

 

1) dp[left][right][color]

재귀함수로 구간에 특정 color로 색칠하는 방법을 고민했다.

=> 실패 이유는 모르겠다.

 

2) dp[left][right]

하지만 구간을 나누고 특정 color로 색칠할 필요가 없었다. => left의 색이나 right의 색으로 칠하는 것이 자명하기 때문이다.

dp[left][right] = min(dp[left][i] + dp[i + 1][right] + (color[left] != color[i + 1]))의 점화식으로 n^3으로 해결할 수 있다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> ve;

vector<vector<int>> dp;
int solve(int l, int r) {
    if (l >= r) {
        return 0;
    }

    if (dp[l][r] != INT32_MAX) {
        return dp[l][r];
    }

    for (int i = l; i < r; ++i) {
        int ll = solve(l, i);
        int rr = solve(i + 1, r);

        dp[l][r] = min(dp[l][r], ll + rr + (ve[l] != ve[i + 1]));
    }

    return dp[l][r];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k;
    ve.resize(n);
    for (auto &i : ve) {
        cin >> i;
    }

    dp.assign(n, vector<int>(n, INT32_MAX));
    cout << solve(0, n - 1) << "\n";
}