[백준] 9251 LCS

November 09, 2021 ( last updated : November 09, 2021 )
DP 알고리즘

https://github.com/sneakstarberry/

Abstract

[백준] 9251번 LCS

[백준] 9251번 LCS

백준 9251번

알고리즘 유형

풀이방법

2개의 경우의 수가 있다. 알파벳이 같을 경우 알파벳이 같지 않을 경우 같을 경우 이전에서 +1 이고 같지 않을 경우 이전까지의 알파벳에서 가장 많이 알파벳이 같을 경우를 선택한다.

#include <iostream>
#include <cmath>
using namespace std;
int DP[1001][1001];
int main()
{
  string a_string, b_string;

  cin >> a_string >> b_string;

  for (int i=1; i<=a_string.size(); i++) {
    for (int j=1; j<=b_string.size(); j++) {
      if(a_string[i-1] == b_string[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[a_string.size()][b_string.size()];
  return 0;
}

Originally published November 09, 2021
Latest update November 09, 2021

Related posts :

{# #}