코드 복사/붙여넣기 하는 당신이 아름답습니다.

9251 : LCS

풀이

dp[i][j] = a[1~i]와 b[1~j]의 LCS 값

dp[i][j] = max(d[i-1][j], d[i][j-1], d[i-1][j-1] + (a[i] == b[j]))

코드

#include <stdio.h>
#include <algorithm>

char a[1111], b[1111];
int i, j, d[1111][1111];

int main() {
	scanf("%s\n%s", a + 1, b + 1);

	for (i = 1; a[i]; i++) for (j = 1; b[j]; j++)
		d[i][j] = std::max({ d[i-1][j], d[i][j-1], d[i-1][j-1] + (a[i] == b[j]) });
	
	printf("%d", d[i-1][j-1]);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-08-08 17:15

Read more posts by this author