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

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

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

 

 

왼쪽의 i 번째 소, 오른쪽의 j 번째 소를 이을려고 할 때 (물론 두 소가 친한 경우에) 어떻게 해야할 까 생각해보니,
DP로 풀면 되겠다고 생각했다.

왜냐하면, i 번째 소, j 번째 소를 이을 때, 
[ 0,0 ] ~ [ i - 1, j - 1 ]  조합 중 가장 많은 소를 연결하는 경우에 더해  i , j 를 잇기만 하면 되기 때문에, DP 라고 생각했다.

 

점화식은 다음과 같다.

친한 소의 경우
$$ DP[i][j] = DP[i-1][j-1] + 1  $$

안 친한 소의 경우
$$ DP[i][j] = max(DP[i][j-1] , DP[i-1][j], DP[i-1][j-1] )  $$

 

코드는 아래와 같다.

#include <cstdio>
#include <algorithm>

int n, ans;
int arr[2000], dp[1000][1000];

bool cmp(int a, int b){ return std::abs(a-b) <= 4; }

int main(){

    scanf("%d",&n);
    for(int i=0;i<2*n;i++) scanf("%d",arr+i);
    
    if(cmp(arr[0], arr[n])) dp[0][0] = 1;
    for(int i=1;i<n;i++){
        if(cmp(arr[0], arr[i+n]) || dp[0][i-1]) dp[0][i] = 1;
        if(cmp(arr[i],arr[n])    || dp[i-1][0]) dp[i][0] = 1;
    }

    for(int i=1;i<n;i++){
        for(int j=1;j<n;j++){
            if(cmp(arr[i], arr[n+j])){ 
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            dp[i][j] = std::max(dp[i][j], std::max(dp[i-1][j-1], std::max(dp[i-1][j], dp[i][j-1])));
            if(dp[i][j] > ans) ans = dp[i][j];
        }
    } 

    printf("%d\n",ans);

    return 0;
}