알파벳 소문자로 구성된 길이 1 이상의 두 문자열 X, Y가 있다. 이 문자열들의 임의의 위치에 공백을 삽입하여 두 문자열의 길이를 같게 만든 다음, 앞에서부터 한 글자씩 살펴보면서, 같은 위치에 있는 두 문자 X[i], Y[i]에 대해서 다음과 같이 점수를 계산한다.
두 문자가 같은 경우에는 A(> 0)점을 받게 된다. 단, 두 문자가 모두 공백인 경우는 허용되지 않는다. 두 문자 중 적어도 하나가 공백인 경우에는 B(< 0)점을 받게 된다. 두 문자가 모두 공백이 아니고 서로 다른 경우에는 C(< 0)점을 받게 된다. 예를 들어 A = 10, B = -1, C = -5인 경우, 다음과 같은 경우들을 살펴보자.
이 경우 앞에서부터 점수를 계산하면 각각 -1, -1, -1, 10점이 되고 따라서 총점은 7점이 된다.
두 문자열이 주어졌을 때, 공백을 적절히 추가했을 때 얻을 수 있는 최대 총점을 구하는 프로그램을 작성하시오.
첫째 줄에 세 정수 A, B, C (0 < A ≤ 10,000, -10,000 ≤ B, C < 0) 가 주어진다. 그리고 둘째 줄에 X가, 셋째 줄에 Y가 주어진다. 각 문자열의 길이는 3,000자를 넘지 않으며 빈 문자열은 입력으로 주어지지 않는다.
출력
첫째 줄에 최대 총점을 출력한다.
입력 예시
10 -1 -5
abc
dc
출력 예시
7
풀이
처음에 파이썬으로 풀이하였을 때 메모리 초과가 뜨는 걸 보고 당황했다... 아마 3000^2의 2차원 리스트가 문제가 되는 모양인데, 그럼 왜 pypy3으로는 풀리는지 의문이다...
무조건 DP문제라고 볼 수 있다. 문자열 X의 i-1번째, 문자열 Y의 j-1번째 문자까지를 전부 사용하였을 때의 최대 점수를 DP[i][j]라고 하자. 이 때, 다음의 경우가 가능하다.
두 문자열을 같이 두기 : 이 때, 두 문자열이 같다면 A 점수, 다르다면 C점수를 받게 된다. DP[i+1][j+1]은 원래 값과 현재 DP[i][j]값 + 매칭 점수 중 최댓값을 가지게 된다.
한 문자열만 사용하기 : 이 때 다른 문자열은 공백이 와야 하므로, DP[i][j+1] 혹은 DP[i+1][j]는 원래 값과 현재 DP[i][j]값 + B점수 중 최댓값을 가지게 된다.
이를 토대로 순회하면, 최종적으로 DP[-1][-1], 즉 DP의 끝부분에 전체 문자열을 사용하였을 때의 최대 점수를 얻을 수 있다. 시간복잡도는 O(len(X) * len(Y))가 된다. 아마 python으로도 아슬아슬하지 않을까 싶다.
풀이 코드 (pypy3)
A, B, C = map(int, input().split())
X = input().strip()
Y = input().strip()
dp = [[-float('inf')]*(len(Y)+1) for _ in range(len(X)+1)]
dp[0][0] = 0
for i in range(len(X)+1) :
for j in range(len(Y)+1) :
if i < len(X) and j < len(Y) :
match_score = A if X[i] == Y[j] else C
dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+match_score)
if i < len(X) :
dp[i+1][j] = max(dp[i+1][j], dp[i][j] + B)
if j < len(Y) :
dp[i][j+1] = max(dp[i][j+1], dp[i][j] + B)
print(dp[-1][-1])
