[C++] 백준 9252번 : LCS 2 (G5)

#문제

www.acmicpc.net/problem/9252

9252번: LCS 2

#풀이 & 학습한 내용

앞서 풀이한 supremo7.tistory.com/97에서 LCS 자체를 추가로 출력해줘야 하는 문제이다. 이를 위해 동선을 역추적하는 배열을 따로 선언하고 재귀를 통해 동선을 출력해준다. if문에서 ==를 =로 적는 실수 하지말자

 

#소스코드

#include<iostream>
#include<algorithm>
#include<cstring>
 
#define NEITHER 0
#define UP 1
#define LEFT 2
#define UP_AND_LEFT 3
 
void trace(int i, int j);
 
using namespace std;
 
int dp[1002][1002];
int track[1002][1002];
char a[1002];
char b[1002];
 
int main(void) {
    
    cin >> a >> b;
    int a_l = strlen(a);
    int b_l = strlen(b);
 
    for (int i = 0; i <= a_l; i++) {
        dp[i][0] = 0;
    }
    for (int i = 0; i <= b_l; i++) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= a_l; i++) {
        for (int j = 1; j <= b_l; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                track[i][j] = UP_AND_LEFT;
            }
            else if (dp[i][j - 1] > dp[i - 1][j]) {
                dp[i][j] = dp[i][j - 1];
                track[i][j] = LEFT;
            }
            else {
                dp[i][j] = dp[i-1][j];
                track[i][j] = UP;
            }
        }
    }
 
    std::cout << dp[a_l][b_l] << '\n';
    trace(a_l, b_l);
    
}
 
void trace(int i, int j) {
    if (i < 0 || j < 0) {
        return;
    }
    if (track[i][j] == UP_AND_LEFT) {
        trace(i - 1, j - 1);
        cout << a[i-1];
    }
    else if (track[i][j] == UP) {
        trace(i - 1, j);
    }
    else {
        trace(i, j - 1);
    }
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_9252.cpp

HoYoungChun/BOJ_algorithm