1. 문제 설명

소가 길을 건너 간 이유 8

2. 문제 분석

DP를 통해 현재 왼쪽-오른쪽 소를 연결하는 지점까지 가장 많은 수의 횡단보도를 기록하자. 횡단보도를 만들 수 있는 기준은 주어진 값의 해당 인덱스 값의 차가 4 이하일 경우다.

3. 나의 풀이

import Foundation

let N = Int(String(readLine()!))!
var leftCows = [0]
var rightCows = [0]
for _ in 0..<N {
    let cow = Int(String(readLine()!))!
    leftCows.append(cow)
}
for _ in 0..<N {
    let cow = Int(String(readLine()!))!
    rightCows.append(cow)
}

var dp = Array(repeating: Array(repeating: 0, count: N+1), count: N+1)

for i in 1..<N+1 {
    for j in 1..<N+1 {
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        if abs(leftCows[i] - rightCows[j]) <= 4 {
            dp[i][j] = dp[i-1][j-1] + 1
        }
    }
}

print(dp[N][N])