문자열의 확장과 거리
시간 제한1초메모리 제한128 MB
두 문자열을 정렬할 때 문자 간 차이와 공백 삽입 비용 K를 이용해 최소 거리를 구하는 편집거리 스타일의 동적 계획법 문제입니다.
문제
문자열 X의 확장이란, X의 임의의 위치(맨 앞과 맨 뒤 포함)에 공백을 원하는 개수(0개, 1개, 또는 그 이상)만큼 끼워 넣어 만든 문자열을 말한다. 예를 들어 X가 'abcbcd'이면 'abcb-cd', '-a-bcbcd-', 'abcd-cd-' 등은 모두 X의 확장이다. (여기서 공백은 '-'로 나타낸다.)
A1을 문자열 A의 확장, B1을 문자열 B의 확장이라 하자. A1과 B1의 길이가 같다면 두 문자열 사이의 거리를 정의할 수 있는데, 이는 같은 위치에 있는 두 문자의 거리를 모두 더한 값이다. 두 문자 사이의 거리는 두 문자의 ASCII 코드 값의 차이이며, 공백과 (공백이 아닌) 다른 문자 사이의 거리는 입력으로 주어지는 K이다.
두 문자열 A와 B가 주어질 때, 길이가 같은 확장 A1과 B1을 잘 골라 두 문자열 사이의 거리를 가장 작게 만들었을 때 그 최소 거리를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 문자열 A, 둘째 줄에 문자열 B가 주어진다. 두 문자열은 모두 알파벳 소문자로만 이루어져 있으며, 길이는 2000 이하이다. 셋째 줄에는 공백과 다른 문자 사이의 거리 K가 주어진다. (1 ≤ K ≤ 100)
출력
첫째 줄에 가능한 가장 작은 거리를 출력한다.