# [Gold III] 소가 길을 건너간 이유 8 [문제 링크](https://www.acmicpc.net/problem/14462) ## 문제 설명 <p>존 (우리가 지금까지 도와 주었던 존과는 다른 인물이다)의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종 (1 ≤ N ≤ 1000)이다. 만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 나쁘다.</p> <p>농장에는 일자형 길이 있고, 양쪽에 목초지가 N개씩 있다. 왼쪽 목초지에는 각 종류의 소가 한 목초지씩 차지하고 있고, 오른쪽도 마찬가지이다. 교통사고를 막기 위해 존은 횡단보도를 설치하려고 한다. 각 횡단보도는 왼쪽과 오른쪽에 있는 목초지를 하나씩 이어야 하고, 길에 수직일 필요는 없다. 물론 사이가 좋은 소들끼리 연결해야 한다. 각 목초지에는 최대 한 개의 횡단보도만 있어야 한다. 그리고 횡단보도가 겹치면 안 된다.</p> <p>그의 농장을 둘러보면서 가능한 한 많이 횡단보도를 설치해주자.</p> ## 입력 <p>첫 줄에 N이 주어진다. 다음 N줄에는 길의 왼쪽에 있는 목초지별로 소의 종 번호가 차례대로 주어진다. 각 종은 한 번씩 나타난다. 그 다음 N줄에는 길의 오른쪽에 있는 목초지가 같은 방식으로 주어진다.</p> ## 출력 <p>조건을 만족하도록 설치할 수 있는 횡단보도의 최대 개수를 출력한다.<br></p> ## 풀이 #### LCS와 유사한 방식의 DP로 해결했습니다. 솔직히 이 풀이보다 이분 매칭이나, LIS 방식이 먼저 떠올랐고, 더 쉬운 것 같습니다. ``` c++ #include<bits/stdc++.h> using namespace std; int a[1001], b[1001], lcs[1001][1001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++) cin >> b[i]; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(abs(a[i]-b[j])<=4) lcs[i][j] = lcs[i-1][j-1]+1; else lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]); } } cout << lcs[n][n]; } ```