3304. 최장 공통 부분 수열

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOHEx66kIDFAWr 

SW Expert Academy

 

분류

동적 계획법(DP)

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

동적 계획법의 대표적인 문제이다.

문제가 낯이 익어서 찾아보니 백준 9251번과 완전히 동일한 내용임을 확인하였다.

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

9251번: LCS

 

시행착오

과거에 백준 9251을 풀었을 때는 많은 시행착오를 겪었던 것으로 기억하지만

이번에는 시행착오 없이 풀 수 있었다.

 

코드

#include<iostream>

using namespace std;

string str[2];
int len[2];
int cache[1001][1001];

int v(int x, int y){
	if (x < 0 || y < 0 || x >= len[0] || y >= len[1]) return 0;
	return cache[x][y];
}

int main(int argc, char** argv){
    int tc, T;
    scanf("%d", &T);
	fill(&cache[0][0], &cache[1000][1000], 0);

    for (tc = 1; tc <= T; ++tc)
    {
		cin>>str[0]>>str[1];
		len[0] = str[0].size();
		len[1] = str[1].size();

		for (int i = 0; i < len[0]; i++){
			for (int j = 0; j < len[1]; j++){
				if (str[0][i] == str[1][j]){
					cache[i][j] = v(i - 1, j - 1) + 1;
				}else{
					int a = v(i - 1, j), b = v(i, j - 1);
					cache[i][j] = a > b ? a : b;
				}
			}
		}

		printf("#%d %d\n", tc, cache[len[0] - 1][len[1] - 1]);
    }

    return 0;
}