백준 C# LCS 9251

해결법

LCS라는 문제에 대한 접근법이 배낭 무게과 연관된 알고리즘
완전탐색과 동시에 서로의 연관성을 판단하기 위해 이전 상위 값에 +1을 한 값을 취하면 됨

현재 배열이 위치한 곳의 숫자는 탐색된 배열 연속된 수의 최대 개수임

 

코드

using System.Collections.Generic;
using System.IO;
using System;
using System.Text;
using System.Linq;

namespace consoleapp1
{
    internal class LCS9251
    {
        //다이나믹 프로그래밍
        //연속성을 판단하기 위해 이전 값에 +1을 취함
        static void Main(string[] args)
        {
            using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
            {
                string str1= sr.ReadLine();
                string str2 = sr.ReadLine();

                int[,] array = new int[str1.Length+1, str2.Length+1];
                
                for(int i = 1; i <= str1.Length; i++)
                {
                    for(int j = 1; j<= str2.Length; j++)
                    {
                        if (str1[i-1] == str2[j-1])
                        {
                            array[i, j] = array[i - 1, j - 1] + 1;
                        }
                        else
                        {
                            array[i, j] = Math.Max(array[i - 1, j], array[i, j - 1]);
                        }
                    }
                }

                //마지막 수는 제일 큰 수 밖에 될 수 없음.
                Console.WriteLine(array[str1.Length, str2.Length]);
            }
        }
    }
}

 

참고[매우 좋은 설명]

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence