전구

#include <iostream>
#include <vector>
#define MAXX 201
using namespace std;
 
int dp[MAXX][MAXX];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, k;
    cin >> n >> k; //k개의 색으로 바꿀 수 있다. 
 
    int color[MAXX] = {0};
 
    for (int i = 1; i <= n; i++) cin >> color[i];
 
    for (int i = 1; i < n; i++) {
        //dp[i][j] = i번 전구와 j번 전구의 색 비교 
        dp[i][i+1] = color[i] == color[i+1] ? 0 : 1;
    }
 
    for (int len = 2; len <= n; len++ ) {
        for (int i = 1; i <= n-len; i++) {
            int j = i+ len;
            for (int k = i; k < j; k++) {
                int tmp = dp[i][k] + dp[k+1][j];
                if (color[i] != color[k+1]) tmp+= 1;
 
                if (!dp[i][j] || tmp < dp[i][j]) dp[i][j] = tmp;
            }
        }
    }
    cout << dp[1][n] << '\n';
 
    return 0;
}