취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2647번 문제인 검은점과 하얀점 연결이다.
문제는 아래 링크를 확인하자.

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

주어진 문자열에서 검은점과 흰점의 개수가 같은 부분구간에 대한 부분문제를 생각할 수 있다.

이를 이용해 식을 잘 세우면 DP를 통해 구간의 높이와 거리합을 저장해가면서 재귀적으로 전체 구간의 최소 거리합을 구할 수 있다.

출력 또한 위 과정에서 역추적할 구간들을 미리 기록해두는 것으로 재귀적으로 가능하다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

int dp[101][101][6]; // dp[L][R][0/1] 0: L부터 R까지 최소거리, 1: 그때 높이 // 3~6: L1 R1 L2 R2
int prefixsum0[101];
int prefixsum1[101];

void func(int L, int R) {
	if (R == L + 1) {
		dp[L][R][0] = 3;
		dp[L][R][1] = 1;
		return;
	}

	int ret = 1000000007, ret_h, retL1, retR1, retL2, retR2;
	if (prefixsum0[R - 1] - prefixsum0[L] == prefixsum1[R - 1] - prefixsum1[L]) {
		if (dp[L + 1][R - 1][0] == 0) func(L + 1, R - 1);
		ret_h = dp[L + 1][R - 1][1] + 1;
		ret = dp[L + 1][R - 1][0] + 2 * ret_h + (R - L);
		retL1 = L, retR1 = R, retL2 = L + 1, retR2 = R - 1;
	}

	for (int r = L + 1; r < R; r += 2) {
		int l = r + 1;
		if (prefixsum0[r] - prefixsum0[L - 1] != prefixsum1[r] - prefixsum1[L - 1]) continue;

		if (dp[L][r][0] == 0) func(L, r);
		if (dp[l][R][0] == 0) func(l, R);
		int temp_h = max(dp[L][r][1], dp[l][R][1]);
		int temp = dp[L][r][0] + dp[l][R][0];
		if (ret > temp) {
			ret = temp, ret_h = temp_h, retL1 = L, retR1 = r, retL2 = l, retR2 = R;
		}
	}

	dp[L][R][0] = ret;
	dp[L][R][1] = ret_h;
	dp[L][R][2] = retL1;
	dp[L][R][3] = retR1;
	dp[L][R][4] = retL2;
	dp[L][R][5] = retR2;
}

void output(int L, int R) {
	if (R == L + 1) {
		cout << L << ' ' << R << '\n';
		return;
	}

	int L1 = dp[L][R][2], R1 = dp[L][R][3], L2 = dp[L][R][4], R2 = dp[L][R][5];

	if ((L1 == L && R1 == R)) {
		cout << L1 << ' ' << R1 << '\n';
		output(L2, R2);
	}
	else {
		output(L1, R1);
		output(L2, R2);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	string s; cin >> s;
	for (int i = 0; i < N; i++) {
		if (s[i] == '0') {
			prefixsum0[i + 1] = prefixsum0[i] + 1;
			prefixsum1[i + 1] = prefixsum1[i];
		}
		else {
			prefixsum1[i + 1] = prefixsum1[i] + 1;
			prefixsum0[i + 1] = prefixsum0[i];
		}
	}

	func(1, N);

	cout << dp[1][N][0] << '\n';
	output(1, N);
}