[BOJ 2449] 전구

https://www.acmicpc.net/problem/2449

"전구!" 다양한 색깔로 전구가 켜져있고, 인접한 색깔의 경우 바뀔때 동시에 바뀐다고 하면 최소한으로 바꾸는 횟수를 정하는 문제이다.DP로 접근하되, 주의할점은 각자가 색깔을 가지고 있다는 점이다.

27번째 줄을 보면 arr[s],arr[i+1]의 값을 비교하는것을 볼 수 있다. 이는 기준을(전구색이 바뀌는 기준을 왼쪽으로) 잡고 그 색깔이 비교해서 같으면 0을 더하고 다르면 1을 더해주는 문제이다. DP문제의 경우 테이블만 정의 잘하면 되는데 언제쯤에 자연스럽게 되련지... 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <stdio.h>
 
#define INF 1e9
typedef long long ll;
using namespace std;
 
int n,k,arr[222],dp[222][222];
 
 
int solve(int s,int e){
    if(s == e)
        return 0;
    int &res = dp[s][e];
    if(res != -1)
        return res;
    res = INF;
    for(int i=s;i<e;i++){
        res = min(res ,(solve(s,i)+solve(i+1,e)+(arr[s]==arr[i+1]? 0:1)));
    }
    return res;
}
 
int main(){
    memset(dp,-1,sizeof(dp));
    cin >> n>> k;
    
    for(int i=1;i<=n;i++){
        cin >>arr[i];
    }
    cout << solve(1,n)<<endl;
    
    return 0;
}