BOJ 17180 - 문자열 비교하기

BOJ 17180 - 문자열 비교하기

단순히 편집거리처럼 풀어줄 수 있다.

$dp[i][j]$ 라면

• $dp[i-1][j-1] + \vert a[i]-b[j] \vert$
• $dp[i-1][j] + \vert a[i-1] - b[j] \vert$
• $dp[i][j-1] + \vert a[i] - b[j-1] \vert$

중 최소로 골라주면 된다.

첫 번째는 두 문자열에서 문자를 늘리지 않고 쓴것이고

두 번째는 $b$에서 문자를 늘린것이고

세 번째는 $a$에서 문자를 늘린것이다.