전구 - 2449

//2449 - 전구
 
#include <iostream>
using namespace std;
 
#define INF 2000
 
int N, M;
int arr[200];
int cache[200][200];
 
void init()
{
    cin >> N >> M;
    for(int i = 0; i<N; ++i)
        cin >> arr[i];
    for(int i = 0; i<N; ++i)
        for(int j = 0; j<N; ++j)
            cache[i][j] = -1;
}
 
int dp(int start, int end)
{
    if(start == end)
        return 0;
    int& ret = cache[start][end];
    if(ret != -1)
        return ret;
    ret = INF;
    for(int mid = start; mid < end; ++mid)
        ret = min(ret, dp(start, mid) + dp(mid+1, end) + (arr[start] == arr[mid+1] ? 0 : 1));
    return ret;
}
 
int main()
{
    init();
    cout << dp(0, N-1);
}

 

 

 

 

 

 

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

2449번: 전구

 

 

 

 

 

 

전구

어려웠습니다..

A[i][j] : [i..j] 구간 전구의 색을 통일하는데 드는 최소비용

A[i][j] : min(i<k<j){A[i][k] + A[k+1][j] + (1 or 0)}

(두 부분문제의 색이 같으면 0, 다르면 1)

 

A[i][j]가 최소가 되게 하는 전구의 색을 알아야 위의 (1 or 0) 을 구할 수 있습니다.

A[i][j]가 't'라는 색으로 통일될때 최소비용이라고 가정하겠습니다.

 

1. 't'는 [i...j]구간의 색중 하나의 색입니다.

2. A[i][j]의 선두부분은 't'와 색이 다른경우 딱 한번만 바꿔 주는것이 최선입니다.

A[i][j]의 색을 통일하는 과정에서 마지막에 하나 중간에 하나 전체 비용에 영향을 주지 않습니다.

3. 2에 의해 최종적으로 A[i][j]는 '선두부분'/'t' 이렇게 두가지 색으로 나눠져 있을 것이고 이는 결국 't'로 통일하나 '선두부분'으로 통일하나 결국 A[i][j] 색을 통일하는 최소비용은 같다는것을 알수 있습니다.

 

따라서 A[i][j]는 A[i]의 색으로 통일하는게 비용이 가장 적게 들고, 따라서 점화식의 (1 or 0) 부분은 A[i]와 A[k+1] 두개의 색을 비교해 선택할 수 있습니다.