[백준 BOJ][DP] 9251 LCS

PS/BOJ

[백준 BOJ][DP] 9251 LCS

Jubil 2018. 7. 18. 23:45

9251_LCS

링크

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

풀이

처음에 편의를 위해서 0행과 0열을 0으로 세팅해줍니다.

DP[i][j]를 LCS(i까지의 string2, j까지의 string1)라고 정의합시다.

LCS로 비교하는 string의 마지막 문자가 같다면,

LCS(i까지의 string2, j까지의 string1) = LCS(i-1까지의 string2, j-1까지의 string1) + 1이 됩니다.

즉, if(string2[i] == string1[j]) DP[i][j] = DP[i-1][j-1] + 1이 됩니다.

LCS로 비교하는 string의 마지막 문자가 다르다면,

LCS(i까지의 string2, j까지의 string1) = max(LCS(i-1까지의 string2, j까지의 string1), LCS(i까지의 string2, j-1까지의 string1))이 됩니다.

즉, if(string2[i] != string1[j]) DP[i][j] = max(DP[i-1][j], DP[i][j-1])이 됩니다.

이렇게 구하게 되면 마지막 DP[n][m]이 우리가 구하고자 하는 LCS(string2, string1) == LCS(string1, string2)가 되는 것이죠.

//9251_LCS

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

int DP[1002][1002]; // LCS(i까지의 string2, j까지의 string1)

int main() {

string string1, string2;

int i, j;

cin >> string1 >> string2;

for (i = 1; i <= string2.size(); ++i) {

for (j = 1; j <= string1.size(); ++j) {

if (string1.at(j - 1) == string2.at(i - 1)) DP[i][j] += DP[i - 1][j - 1] + 1;

else DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);

}

for (i = 0; i <= string2.size(); ++i) {

for (j = 0; j <= string1.size(); ++j) {

cout << DP[i][j] << " ";

}

cout << endl;

}

cout << DP[i - 1][j - 1] << endl;

return 0;

}

Colored by Color Scripter

이렇게 해서 DP 표를 출력해보면, 위의 사진과 동일한 결과를 출력합니다.

코드