[백준] 2449 전구

문제 링크

http://icpc.me/2449

2449번: 전구

풀이

오랜만에 되게 재밌게 푼 dp문제다.

3차원 dp로 풀었는데 다른 사람 코드 구경하면서 2차원 dp로 내 풀이보다 훨씬 쉽게 풀 수 있는 걸 발견했다. 이 글에선 3차원 풀이를 작성하겠다.

시간 복잡도는 O(N^3 * K)에 해결할 수 있다.

dp[l][r][i] : 구간 [l, r]을 i로 만들었을 때 최소 경우의 수

a[i] : a번째 전구의 색

위와 같이 정의를 하면 세 가지 케이스로 점화식을 세울 수 있다.

1. [l, r -1] 또는 [l+1, r]에서 파생된 경우

r이 i이거나 a[r-1] == a [r]이어서 이미 색이 i로 바뀐 경우와, [l+1, r]에서 l이 i이거나 a[l] == a [l+1]이어서 이미 색이 i로 바뀐 경우를 처리해야 한다.

dp[l][r][i] = min(dp[l][r - 1][i] + !(a[r] == i || a[r] == a[r - 1]), dp[l + 1][r][i] + !(a[l] == i || a[l] == a[l + 1])))

 

2. [l, r]이 x로 모두 색칠 된 경우에서 i로 색칠하는 경우

dp[l][r][i] = min(dp[l][r][x] + 1) (1 <= x <= k, x != i)

 

3. [l, r]을 [l, mid], [mid + 1, r]로 나눠 색칠하는 경우

dp[l][r][i] = min(dp[l][mid][i] + dp[mid + 1][r][i]) (l <= mid <= r - 1)

코드

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

int dp[202][202][22];
int arr[202];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][i][j] = (arr[i] != j);
        }
    }
    for (int d = 1; d <= n - 1; d++) {
        for (int l = 1; l <= n; l++) {
            int r = l + d;
            if (r > n) continue;
            for (int i = 1; i <= k; i++) {
                dp[l][r][i] = min(
                    dp[l][r - 1][i] + !(arr[r] == i || arr[r] == arr[r - 1]), 
                    dp[l + 1][r][i] + !(arr[l] == i || arr[l] == arr[l + 1]));
                for (int mid = l; mid <= r - 1; mid++) 
                    dp[l][r][i] = min(dp[l][r][i], dp[l][mid][i] + dp[mid + 1][r][i]);
            }
            int mn = *min_element(&dp[l][r][1], &dp[l][r][k + 1]);
            for (int i = 1; i <= k; i++) dp[l][r][i] = min(dp[l][r][i], mn + 1);
        }
    }
    int ans = 1e9;
    for (int i = 1; i <= k; i++) ans = min(ans, dp[1][n][i]);
    cout << ans;
}