백준 14462, 소가 길을 건너간 이유 8

문제

백준 14462번

풀이

dp[l][r] = 왼쪽 목초지를 l까지, 오른쪽 목초지를 r까지 봤을 때의 최대 개수로 점화식을 세우겠습니다.

 

dp table을 채우는 방법을 생각해보겠습니다.

l과 r을 모두 방문하면서 dp[l][r]을 구성할 때 dp[l - 1][r] 또는 dp[l][r - 1]이 그대로 오는 경우가 답이 될 수 있습니다.

또는, 횡단보도를 놓을 수 있는 경우가 있습니다. ($ | left[l] - right[r] | <= 4 $) 이 때는 dp[l - 1][r - 1] + 1이 dp[l][r]이 될 수 있습니다.

 

모든 $ i $와 $ j $에 ($ 1 <= i, j <= N $) 방문하므로 시간 복잡도는 $ O(N^2) $이 됩니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

int l[1001], r[1001], dp[1001][1001];

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> l[i];
	for (int i = 1; i <= n; i++) cin >> r[i];

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			if (abs(l[i] - r[j]) <= 4) dp[i][j] = dp[i - 1][j - 1] + 1;
		}

	cout << dp[n][n];
}