[C++] 백준 2216 문자열과 점수

문제

알파벳 소문자로 구성된 길이 1 이상의 두 문자열 X, Y가 있다. 이 문자열들의 임의의 위치에 공백을 삽입하여 두 문자열의 길이를 같게 만든 다음, 앞에서부터 한 글자씩 살펴보면서, 같은 위치에 있는 두 문자 X[i], Y[i]에 대해서 다음과 같이 점수를 계산한다.

1. 두 문자가 같은 경우에는 A(> 0)점을 받게 된다. 단, 두 문자가 모두 공백인 경우는 허용되지 않는다.
2. 두 문자 중 적어도 하나가 공백인 경우에는 B(< 0)점을 받게 된다.
3. 두 문자가 모두 공백이 아니고 서로 다른 경우에는 C(< 0)점을 받게 된다.

 

입력

첫째 줄에 세 정수 A, B, C (0 < A ≤ 10,000, -10,000 ≤ B, C < 0) 가 주어진다. 그리고 둘째 줄에 X가, 셋째 줄에 Y가 주어진다. 각 문자열의 길이는 3,000자를 넘지 않으며 빈 문자열은 입력으로 주어지지 않는다.

 

출력

첫째 줄에 최대 총점을 출력한다.

 

 

구현

알고리즘 시간에 배운 Sequence Alignment 를 이용해서 풀었다.

 

가장 중요한 점은 현재 문자가 같지 않아도 고를 수 있는 선택지가 3가지 있다는 것이다.

 

현재 보고있는 문자를 X[i] , Y[j] 라고 해보자,

 

1.  X[i] == Y[j] 의 경우
   
   • X[i -1] , Y[j -1] 의 점수에서 +A를 해주면 된다. (둘다 현재 문자를 보기 전의 상태 + A)
2. X[i] != Y[j]의 경우
   • X[i]를 공백으로 둔다. -> X[i-1]의 값에서 +B를 해주면 된다. (Y[j]문자는 채택하고 X[i]문자는 공백)
   • Y[j]를 공백으로 둔다. -> 위와 반대다
   • 서로 다른 경우로 둔다. -> X[i-1], Y[j-1]의 점수에서 +C를 해주면 된다.

 

점화식의 감이 올 것이다.

 

if (X[i] == Y[j] {
  DP[i][j] = DP[i - 1][j - 1] + A; // 두 문자가 일치할 경우
} else {
  DP[i][j] = max(DP[i][j - 1] + B, DP[i - 1][j] + B); // 한 문자를 공백으로 둘 경우
  DP[i][j] = max(DP[i][j], DP[i - 1][j - 1] + C) // 다른 문자로 처리할 경우
}

 

 

DP의 행은 X, 열은 Y로 해서 2차원 배열을 만들었다. 

 

0번째 행과 0번째 열은 B * i 초기화를 해주어야 한다. 왜냐? 아예 선택을 안하는 경우도 고려해야하기 때문이다.

 

끝! 난줄 알았는데 이런 메모리 제한이 128MB다.

 

문자가 3000글자까지 들어올 수 있으니 3000*3000 int 배열은 바로 메모리 초과가 나버린다.

 

하지만 굳이 2차원 배열 전체를 쓸 필요는 없다. 위의 코드에서 보았듯 우리는 앞 행과 현재 행만 사용하기 때문이다.

 

-> 1차원 배열 2개를 계속 재사용하면 된다. 

 

 

전체 구현

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int A, B, C; // 같은 경우, 공백, 다른 경우
string X, Y; // 비교할 문자열;

void Print(vector<int> &dp) {
	for (int i = 0; i < X.size() + 1; i++) {
		cout << dp[i] << " "; 
	}
	cout << endl;
}

void Dp(vector<int> &dp) {
	for (int i = 1; i < Y.size() + 1; i++) {
		vector<int>temp(X.size() + 1, 0);
		temp[0] = i * B;
		for (int j = 1; j < X.size() + 1; j++) {
			if (Y[i - 1] == X[j - 1]) {
				temp[j] = dp[j - 1] + A;
			} else {
				temp[j] = max(dp[j] + B, temp[j - 1] + B);
				temp[j] = max(temp[j], dp[j - 1] + C);
			}
		}
		dp = temp;
	}
}

void Initial(vector<int> &dp) {
	for (int i = 0; i < X.size() + 1; i++) {
		int val = i * B;
		dp[i] = val;
	}
}

int main(void) {
	cin >> A >> B >> C;
	cin >> X;
	cin >> Y;

	vector<int>dp(X.size() + 1, 0);
	Initial(dp);
	Dp(dp);
	cout << dp[X.size()];
}