[백준 9251] LCS

[백준 9251] LCS

문제 링크

using namespace std;
string text1, text2;
int dp[1004][1004];
void solve() {

  for(int i=1; i<=text1.length(); i++) {
    for(int j=1; j<=text2.length(); j++) {
      if(text1[i-1] == text2[j-1]) {
        dp[i][j] = dp[i-1][j-1] + 1;
      } else {
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }

  cout << dp[text1.length()][text2.length()];
}

int main() {

  cin >> text1 >> text2;

  solve();

  return 0;
}

• 해당 그림에서 볼 수 있다시피 인덱스를 1부터 시작한다 (i-1, j-1 처리를 위해)
• 만약 text1[i]와 text2[j]가 같다면, 하나가 더 길어진 것이기 때문에 +1을 해 준다.
• 같지 않다면, 이전의 값에서의 최댓값으로 업데이트 해 준다.