[백준 2449] 전구 C++

2449번: 전구

1. 문제풀이 아이디어

전구를 A, B 두 부분으로 나누고, A의 시작 지점의 색깔과 B의 시작 지점의 색깔을 재귀적으로 같게 한다면 A, B 모두 같은 색이 될 것이다..

 - A부분의 색을 같게 하는데 필요한 작업의 수 + B부분의 색을 같게 하는데 필요한 작업의 수 + 현재 A, B의 첫 번째 전구의 색을 같게 하는데 필요한 작업의 수

 

2. 코드 설명

dp[st][ed] : 전구 배열에서 st부터 ed까지의 전구를 모두 같은 색으로 맞추는데 필요한 최소 횟수

int temp = (bright[st] == bright[i+1]? 0 : 1);

-> 현재 A, B의 첫 번째 전구의 색을 같게 하는데 필요한 작업의 수

ret = min(ret, solve(st, i) + solve(i + 1, ed) + temp);

-> dp[st][ed] = A에 필요한 작업의 수 + B에 필요한 작업의 수 + 현재 필요한 작업의 수

#include <iostream>
#include <cstring>
#define INF 1e9+7
using namespace std;
 
int N, K;
int bright[202];
int dp[201][201];
 
int solve(int st, int ed){
    if(st == ed) return 0;
    
    int &ret = dp[st][ed];
    if(ret != -1) return ret;
    
    ret = INF;
    
    for(int i = st; i < ed; i++){
        int temp = (bright[st] == bright[i+1]? 0 : 1);
        ret = min(ret, solve(st, i) + solve(i + 1, ed) + temp);
    }
    
    return ret;
}
 
int main(){
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        cin >> bright[i];
    }
    memset(dp, -1, sizeof(dp));
    
    cout << solve(0, N-1);
    return 0;
}

분할 정복 + 동적계획법의 메모이제이션

 

dp문제는 아이디어를 떠올리기가 정말 어려운 것 같다

부분 문제를 어떻게 구성 할지(어떤 정보를 메모이제이션 해야하는지)가 가장 찾기 어렵다..