문자열 a와 b가 주어졌을 때, a에 연산을 최소 횟수로 수행해 b로 만들고자 한다.

a에 적용할 수 있는 연산은 총 3가지이며 아래와 같다.

  • 연산

  1. 삽입(Add): a의 한 위치에 문자 하나를 삽입, 이 때의 비용은 5가 발생한다.

  2. 삭제(Delete): a의 문자 하나 삭제, 이 때의 비용은 5가 발생한다.

  3. 교체(Replace): a의 문자 하나를 다른 문자로 교체. 이 때의 비용은 다음과 같이 발생한다.

(a) 대소문자만 다른 경우(예. a와 A): 1

(b) 둘 다 숫자인 경우(예. 3과 5): abs(a[i] - b[j]) = abs(3 – 5) = 2

(c) 하나는 알파벳, 다른 하나는 숫자인 경우(예. a와 3): 7

(d) 둘 다 알파벳이면서 다른 경우(예. a와 c): 5

(e) 동일한 경우: 0

두 문자열이 주어졌을 때, 최소 비용(최소 편집 횟수)를 구하는 프로그램을 작성하시오.

(입력)

첫째 줄에 a, 두번째 줄에 b가 입력으로 주어진다.

(출력)

최소 비용(최소 편집 횟수)를 출력하시오.

(예제 1)

  • 입력

abc

aBc

  • 출력

1

(예제 2)

  • 입력

123

a129

  • 출력

11

(예제 3)

  • 입력

abc123

abcd

  • 출력

17