BOJ2449: 전구 작성일 2020-05-31 https://www.acmicpc.net/problem/2449 범위 위주의 DP 솔직히 점화식 도출해내는게 쉽지는 않다. 12345678910111213141516171819202122232425#include <bits/stdc++.h> using namespace std; int N, K; vector<int> arr; vector<vector<int>> dp; int go(int s, int e) { if(dp[s][e] != -1) return dp[s][e]; int ans = INT_MAX; for(int i = s+1; i < e; i++) if(arr[i] != arr[i-1]) ans = min(ans, go(s, i) + go(i, e) + (arr[s] != arr[i])); if(ans == INT_MAX) return dp[s][e] = 0; return dp[s][e] = ans; } int main() { cin >> N >> K; arr.resize(N); dp.resize(N, vector<int>(N+1, -1)); for(int i = 0; i < N; i++) cin >> arr[i]; cout << go(0, N); }