세 문자열의 LCS
면접 대비시간 제한2초메모리 제한128 MB
세 문자열에 공통으로 존재하는 최장 공통 부분열의 길이를 동적 계획법으로 구하는 문제입니다.
문제
세 문자열이 주어질 때, 세 문자열 모두에 공통으로 나타나는 부분 수열 중 가장 긴 것의 길이를 구하라.
부분 수열은 원래 문자열에서 문자를 일부 지우되, 남은 문자의 상대적인 순서는 그대로 유지해 얻을 수 있는 문자열이다.
입력
첫째 줄에 첫 번째 문자열, 둘째 줄에 두 번째 문자열, 셋째 줄에 세 번째 문자열이 주어진다.
세 문자열은 모두 알파벳 소문자로만 이루어져 있으며, 각 문자열의 길이는 100 이하이다.
출력
세 문자열의 LCS 길이를 첫째 줄에 출력한다.