9251번 LCS

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

41, 42, 43, 45, 46, 47번 째 줄 순서 중요하다.

41 ~ 43 : 41, 42 두 경우 모두 아닌 경우에만 43이 실행되어야 한다.

#include <bits/stdc++.h>
 
using namespace std;
 
int lcs[1010][1010] = { 0, };
 
string str1, str2;
 
int main(void)
{
    string input1, input2;
 
    cin >> input1 >> input2;
 
    str1 = '0' + input1;
    str2 = '0' + input2;
 
    int len1 = str1.length();
    int len2 = str2.length();
 
    for (int i = 0; i < len1; i++)
        for (int j = 0; j < len2; j++)
        {
            if (i == 0 || j == 0)
            {
                lcs[i][j] = 0;
                continue;
            }
 
            if (str1[i] == str2[j]) lcs[i][j] = lcs[i - 1][j - 1] + 1;        
            else lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);        
        }
 
    int i = len1 - 1;
    int j = len2 - 1;
 
    stack<int> st;
 
    while (lcs[i][j] != 0)
    {
        if (lcs[i][j] == lcs[i][j - 1]) --j;
        else if (lcs[i][j] == lcs[i - 1][j]) --i;
        else if (lcs[i][j] - 1 == lcs[i - 1][j - 1])
        {
            st.push(i);
            --i;
            --j;
        }
    }
 
    printf("%d\n", lcs[len1 - 1][len2 - 1]);
 
    return 0;
}