고양이 두 잔

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 풀이 조금 헷갈리지만 일단은 동적 계획법 문제이다. 그걸 몰랐으면 순열로 모든 부분수열을 순회하려고 했을 것 같다. 문제를 보고 이게 뭘로 풀 때 더 효율적인 유형인가 판단하는 것도 능력일 듯. 어쨌거나 주어진 두 문자열에 대해서 각각 처음부터 끝까지 순회하며 ..