백준 - 9252 LCS2

 

해결과정 - DP

전형적인 DP문제였는데 문자까지 머신러닝에서 배웠던 어떤 기법과 유사했는데 이름이 기억이 안난다.

아이디어는 문자열 a, b가 있는경우 a[0]과 b[0 ~ max]까지 비교 그다음은 a[:1]과 b[0 ~ max]까지 비교하는것 즉 a의 길이를 1씩 늘려가며 차근차근 긴 문자열을 찾아가는 과정이였다. 문자의 경우 내가 찾은 문자면 dp[i][j] 가 dp[i -1][j]와 dp[i][j-1]보다 큰 경우다.

 

#include <bits/stdc++.h>

#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;

int dp[1001][1001];

int main() {
    FAST;
    string a, b;
    cin >> a >> b;
	
    int n = a.size(), m = b.size();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int first = dp[i-1][j-1] + (a[i-1] == b[j-1]);
            int second = dp[i-1][j];
            int third = dp[i][j-1];
            
            if (first > second && first > third) {
				dp[i][j] = first;
            }
            else if (second > third) {
				dp[i][j] = second;
            }
            else {
				dp[i][j] = third;
			}
        }
    }

    cout << dp[n][m] << '\n';

    if (dp[n][m] != 0) {
        int i = n, j = m;
        string ans = "";
        while (i > 0 && j > 0) {
            if (dp[i][j] == dp[i - 1][j]) {
                i--;
            }
            else if (dp[i][j] == dp[i][j - 1]) {
                j--;
            }
            else {
                ans = a[i - 1] + ans;
				i--, j--;
            }
        }
        cout << ans;
    }
    return 0;
}

 

후기

사실 처음에 string도 dp로 만들었는데 메모리 초과가 발생했다 ㅎㅎ