문자열과 점수
면접 대비시간 제한2초메모리 제한128 MB
두 문자열을 정렬할 때 매칭, 공백, 불일치에 점수를 매겨 최대 점수를 구하는 전형적인 서열 정렬 DP 문제입니다.
문제
알파벳 소문자로 이루어진 빈 문자열이 아닌 두 문자열 X와 Y가 있다. 두 문자열의 문자 사이와 양 끝에 공백을 원하는 만큼 삽입할 수 있다. 삽입한 뒤에는 두 문자열의 길이가 같아야 하며, 같은 위치의 두 문자가 모두 공백인 경우는 허용되지 않는다.
각 위치에서 마주 보는 두 문자로 다음 점수를 얻는다.
- 두 문자가 같은 소문자이면 A점을 얻는다.
- 두 문자 중 정확히 하나가 공백이면 B점을 얻는다.
- 두 문자가 모두 소문자이고 서로 다르면 C점을 얻는다.
A = 10, B = -1, C = -5일 때 아래처럼 정렬할 수 있다.
이 정렬의 각 위치 점수는 차례대로 -1, -1, -1, 10점이므로 총점은 7점이다.
두 문자열 X와 Y가 주어졌을 때, 공백을 적절히 삽입해 얻을 수 있는 최대 총점을 구하시오.
입력
첫째 줄에 세 정수 A, B, C가 주어진다. 이때 0 < A <= 10,000이고, -10,000 <= B, C < 0이다.
둘째 줄에 문자열 X가, 셋째 줄에 문자열 Y가 주어진다. X와 Y는 알파벳 소문자로만 이루어져 있으며, 각 문자열의 길이는 1 이상 3,000 이하이다.
출력
첫째 줄에 만들 수 있는 최대 총점을 출력한다.