9252 : LCS 2

풀이

http://codersbrunch.blogspot.kr/2016/12/9252-lcs-2.html

코드

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

int dp[1234][1234];
char s1[1234], s2[1234];

void f(int i, int j) {
	if (!dp[i][j]) return;
	if (s1[i] == s2[j]) {
		f(i-1, j-1);
		putchar(s1[i]);
	}
	else dp[i-1][j] > dp[i][j-1] ? f(i-1, j) : f(i, j-1);
}

int main() {
	scanf("%s\n%s", s1 + 1, s2 + 1);

	int i, j;
	for (i = 1; s1[i]; i++) for (j = 1; s2[j]; j++)
		dp[i][j] = std::max({ dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+(s1[i]==s2[j]) });

	printf("%d\n", dp[--i][--j]);
	f(i, j);

	return 0;
}

아무말

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

wookje.kwon's profile image

wookje.kwon

2018-02-15 20:30

Read more posts by this author