백준 2449 전구 혼내주기

 

 

구간의 맨 왼쪽 전구 색을 c라고 하면, [l,r]구간을 c로 통일시키는 최소 횟수를 구하려고 했다. 그래서 구간을 색 c와 c가 아닌 구간으로 나눠서 재귀적으로 c가 아닌 구간들의 값을 구해서 더하려고 했는데 삽질을 아주 오래 하고 안풀렸다...

결국 sds 특강 강사님의 설명을 듣고 풀었다. 굳이 색에 집착하지 않아도 되었던 것, 그리고 구간을 나누는 것도 n이 200이기 때문에 다 해봐도 되는 것이었다...
아이디어가 완벽하진 않았지만 큰 흐름은 잡았다는데 위안을 삼고 있다 ㅠ

dp는 역시 어렵다. 심지어 KOI 초등학교 문제다.
나는 언제쯤 초등학교를 졸업할 수 있을까?

 

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int cache[201][201];
int arr[200];
int n, k;

void input() {
    cin >> n >> k;
    for(int i = 0; i < n; ++i) cin >> arr[i];
}

// l~r 구간을 통일시키는 최소 횟수
int d(int l, int r) {
    
    int& ret = cache[l][r];
    if(ret != -1) return ret;

    if(l == r) return ret = 0;

    ret = 2e9;
    for(int i = l; i < r; ++i) {
        int cur = d(l, i) + d(i+1, r);
        if(arr[i+1] != arr[l]) cur++;
        ret = min(ret, cur);
    }
    return ret;
}

int main() {
    fastio;
    input();
    memset(cache, -1, sizeof(cache));
    cout << d(0, n-1);
}