https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 문제 분석 LCS란 최장 공통 부분수열이다. 만약 문자열이 두 개(예제 입력 1의 위 두 문자열)라고 가정하였을 때, 다이나믹 프로그래밍(DP)를 사용하여 쉽게 LCS를 계산할 수 있다. 위의 그림과 같이 두 문자열을 앞에 공백이 있는 이차원 리스트로 만든다. 그 후 이중 반복문을 돌면서 같은 문자열이 있는지 탐색한다. 1. 같은 문자를 만난 경우 이 때, 같은 문자를 만난다면 대각선 왼쪽 위에 있는 수에 1을..