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

문제 타이틀, 문제 스토리도 귀엽지만, 문제 풀이의 알고리즘을 찾기 쉽지 않다.

문제를 보고 바로 다이내믹 프로그래밍 알고리즘으로 문제를 풀어야 함을 떠올려야 하는 것이 중요한 포인트였다.

 

lcs와 비슷한 방법으로 풀었는데,

n=int(input())
left=[0]+[int(input()) for _ in range(n)]
right=[0]+[int(input()) for _ in range(n)]
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        if abs(left[i]-right[j])<=4:
            dp[i][j]=dp[i-1][j-1]+1
print(dp[n][n])

이중 for문으로 left 와 right의 모든 좌표들을 돌면서, 전 index 중에서 더 큰 값을 input 받고, 서로 4이상 차이가 안 난다면, +1을 한다.

되게 classic한 DP 문제인데, 이렇게 어렵다니