백준2647 검은점과 하얀점 연결

작성일 | In

문제 링크

  • http://icpc.me/2647

문제 출처

  • 1999 전국 본선 고등부1

사용 알고리즘

  • DP

시간복잡도

  • O(N3)

풀이

범위 최대 100이고, 쭉쭉 짝을 짓는 다는 것에서 구간DP 느낌이 왔습니다.

val[i][j] = [i, j] 구간에서의 정답, h[i][j] = [i, j] 구간에서의 최대 높이라고 정의합시다.
dp[i][j] = {val[i][j], h[i][j]}라고 정의합시다.
idx[i][j] = [i, j] 구간에서 i와 매칭된 점의 번호라고 정의합시다.

최솟값은 평범한 구간DP문제처럼 쉽게 구할 수 있습니다.

정답을 역추적하는 과정을 봅시다.

  1. 우리는 이미 [i, j]에서 i번 점이 어떤 점과 매칭되는지 (k = idx[i][j])에 저장했습니다.
  2. i와 k는 이미 매칭이 되었습니다.
  3. 매칭되는 구간은 겹치지 않으니까 [i+1, k-1], [k+1, j] 구간을 각각 따로 봐주면 됩니다.

자세한 구현은 코드를 참고하시면 됩니다.

전체 코드

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

int n;
int v[111];
int idx[111][111];
p dp[111][111]; //{val, height}

p f(int s, int e){ //[s, e] 범위
	if(s > e) return {0, 0};
	if(dp[s][e].x != -1) return dp[s][e];
	dp[s][e].x = 0;

	int val = 1e9+7, h = 0;

	for(int k=s+1; k<=e; k+=2){
		if(v[s] != v[k]){
			//s, k 매칭
			p a = f(s+1, k-1); //왼쪽
			p b = f(k+1, e); //오른쪽
			int dist = k - s;
			if(val > a.x + b.x + dist + (a.y + 1) * 2){
				val = a.x + b.x + dist + (a.y + 1) * 2;
				h = max(a.y+1, b.y);
				idx[s][e] = k;
			}
		}
	}
	return dp[s][e] = {val, h};
}

void trace(int s, int e){
	if(s > e) return;
	int k = idx[s][e];
	cout << s+1 << " " << k+1 << "\n";
	trace(s+1, k-1);
	trace(k+1, e);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	string s; cin >> n >> s;
	for(int i=0; i<n; i++) v[i] = s[i] - '0';

	for(int i=0; i<n; i++) for(int j=0; j<n; j++) dp[i][j].x = -1;

	cout << f(0, n-1).x << "\n";
	trace(0, n-1);
}