[BOJ 14462] 소가 길을 건너간 이유 8

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

14462번: 소가 길을 건너간 이유 8

 

- 문제 요약

 

존의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종 (1 ≤ N ≤ 1000)이다.

만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 나쁘다.

농장에는 일자형 길이 있고, 양쪽에 목초지가 N개씩 있다.

왼쪽 목초지에는 각 종류의 소가 한 목초지씩 차지하고 있고, 오른쪽도 마찬가지이다.

교통사고를 막기 위해 존은 횡단보도를 설치하려고 한다.

각 횡단보도는 왼쪽과 오른쪽에 있는 목초지를 하나씩 이어야 하고, 길에 수직일 필요는 없다.

물론 사이가 좋은 소들끼리 연결해야 한다.

각 목초지에는 최대 한 개의 횡단보도만 있어야 한다. 그리고 횡단보도가 겹치면 안 된다.

그의 농장을 둘러보면서 가능한 한 많이 횡단보도를 설치해주자.

 

 

- 알고리즘 정리

 

왼쪽 목초지를 i, 오른쪽 목초지를 j라고 했을 때, 나올 수 있는 길의 경우의 수는 3가지가 있습니다.

(i랑 j 연결, i+1 / j+1), (i만 다음으로, i+1 / j), (j만 다음으로, i / j+1)
dp[i][j] : 현 위치에서의 최대 횡단보도 갯수

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 1001
int n,arr[MAX],brr[MAX],dp[MAX][MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	for(int i=1;i<=n;i++){
		cin>>brr[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(arr[i]-brr[j])<=4){
				dp[i][j]=dp[i-1][j-1]+1;
			}
		}
	}
	cout<<dp[n][n];
}

코드 제출 결과