백준 9251 LCS

// 다시 풀기
 
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
 
string s1, s2;
int d[1001][1001] ;
 
int dp(int a, int b) {
    if (a < 0 || b < 0) return 0;
    if (d[a][b] != -1) return d[a][b];
    return d[a][b] = max({ dp(a - 1, b), dp(a, b - 1), dp(a - 1, b - 1) + (s1[a] == s2[b]) });
}
 
int main() {
    cin >> s1;
    cin >> s2;
    memset(d, -1, sizeof(d));
    printf("%d\n", dp(s1.size() - 1, s2.size() - 1));
    return 0;
}
 
 

내겐 상당히 까다로웠던 문제.

Top-Down 방식의 DP로 접근.

1. string으로 문자열 입력받기

string대신에 char s1[1001]로 입력받을 경우 문자열 길이를 구하기가 까다로워진다.

string을 사용하면 

A. 문자열 입력받기 편하고 cin >> s1;

B. 배열처럼 인덱스로 접근할 수 있고 s1[a] == s2[b]

C. 길이를 쉽게 구할 수 있다. s1.size()

2. memoization을 0이 아닌 -1로 초기화하기.

int d[1001][1001] ;

memset(d, -1, sizeof(d));

cstring 라이브러리를 include하여 memset으로 -1로 초기화 해준다.

보통 배열을 0으로 초기화하지만 이 경우에는 d[i][j] 가 0인 경우가 필요하므로 

한번도 참조하지 않았다는 의미에서 -1로 초기화 해준다.

3. max() 로 삼중 비교하기

max()는 두개의 인자를 받으므로 두 수만 비교가능한 것으로 알고 있다.

물론, max()를 겹쳐서 삼중 비교가 가능하지만 다음과 같이 {} 안에 써주면 삼중비교가 가능하다.

max({ dp(a - 1, b), dp(a, b - 1), dp(a - 1, b - 1) + (s1[a] == s2[b]) });