백준 1958 c++ "LCS 3" -PlusUltraCode-

https://www.acmicpc.net/problem/1958

 

[필자 사고]

LCS 에서 차원이 늘어난 문제이다.

핵심 원리는 동일하다

같은 문자열이 있으면 [i-1][k-1] 의 값에 1을 더해주고

다른 문자열이면 그동한 만든 갯수의 최대값을 갱신하면서 오면 된다.다만 필자가 이 문제를 풀면서 실수한 점은 string str1 에서 str1.insert(0," "); 으로 앞부분에 빈공간을 넣어준뒤str1.size() 형태로 접근해야되는데 <=str1.size() 형태로 접근해서 의도치 않은 outofBounds 가 발생했다.주의하자.

 

아래는 자세한 코드 해설이다.

[코드 해설]

 DP 테이블 초기화

세 개의 문자열이 각각 최대 길이 100이기 때문에, 크기가 101x101x101인 3차원 정수 배열을 만듭니다.
이 배열의 각 위치는 dp[i][j][k]라고 했을 때,
문자열 1의 i번째 문자까지, 문자열 2의 j번째 문자까지, 문자열 3의 k번째 문자까지 고려했을 때의
최장 공통 부분 수열의 길이를 저장합니다.

---

DP 계산 단계

세 문자열의 문자들을 하나씩 살펴보면서, 세 개의 중첩 반복문을 돌립니다.

• 세 문자열의 각 위치의 문자가 모두 같다면, 그 문자를 공통 수열에 추가할 수 있으므로
  dp[i][j][k] = dp[i-1][j-1][k-1] + 1로 값을 갱신합니다.
  이는 이전 위치까지의 공통 수열 길이에 1을 더한 값입니다.
• 세 문자가 하나라도 다르다면, 공통 수열에 추가할 수 없으므로
  셋 중 하나의 문자를 제외하고 계산한 결과 중 최댓값을 사용합니다.
  즉, 이전 상태 세 가지(i-1, j-1, k-1 방향) 중에서 가장 큰 값을 선택합니다.

각 단계마다 갱신된 최댓값을 따로 저장하여 추적합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

string str1, str2, str3;
vector<vector<vector<int>>> dp;

void Input() {
	cin >> str1 >> str2 >> str3;
	str1.insert(0, " ");
	str2.insert(0, " ");
	str3.insert(0, " ");
	dp.assign(101, vector<vector<int>>(101, vector<int>(101)));
}

void Game_Start() {

	int resultCount = 0;

	for (int i = 1; i < str1.size(); i++) {
		for (int k = 1; k < str2.size(); k++) {
			for (int t = 1; t < str3.size(); t++) {
				if (str1[i] == str2[k] && str2[k] == str3[t]) {
					dp[i][k][t] = dp[i - 1][k - 1][t - 1] + 1;
				}
				else {
					dp[i][k][t] = max({
						dp[i - 1][k][t],
						dp[i][k - 1][t],
						dp[i][k][t - 1]
						});

					
				}
				resultCount = max(resultCount, dp[i][k][t]);
			}
		}
	

	}
	cout << resultCount;
}
int main(void) {

	Input();
	Game_Start();
}