전구 - 2449
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
//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);
}
|
cs |
https://www.acmicpc.net/problem/2449
2449번: 전구
입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전구의 색이 전구번호의 순서대로 하나의 정수로 하나의 빈칸을 사이에 두고 주어진다.
www.acmicpc.net
전구
어려웠습니다..
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] 두개의 색을 비교해 선택할 수 있습니다.
