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

#문제

www.acmicpc.net/problem/9251

9251번: LCS

#풀이 & 학습한 내용

index가 0부터 시작하게 설정한 것이 있고, 1부터 시작하게 설정한 것이 있어 확실히 정리해두고 코딩하지 않으면 매우 헷갈린다. 두 문자열의 마지막을 기준으로 생각하여 경우를 나누고 optimal substructure를 구해서 for문을 통해 구현했다. strlen을 사용하기 위해 #inlcude<cstring>을 추가해줬다.

 

#소스코드

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
int dp[1002][1002];
 
int main(void) {
    char a[1002];
    char b[1002];
    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;
            else
                dp[i][j] = max({ dp[i][j - 1],dp[i - 1][j] });
        }
    }
 
    cout << dp[a_l][b_l] << '\n';
    
}

 

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

HoYoungChun/BOJ_algorithm