92511 백준 9251번 : LCS[java] 1. 첫 번째 문자열(s1)과 두 번째 문자열(s2)를 입력받는다. 2. dp에 사용할 배열 dp[1001][1001]을 만든다. ㄴ dp[i][j]는 s1의 i번째와 s2의 j번째 문자까지 비교했을 때 최장 공통 부분수열이다. 3. s1의 i번째 문자와 s2의 j번째 문자를 비교하고 같다면 dp[i][j] = dp[i-1][j-1] +1 이고, → s1의 i번째 문자와 s2의 j번째 문자를 이번 dp[i][j]에서 공통 문자로 사용했기 때문에 직전까지의 최댓값에 +1을 한다. 4. s1의 i번째 문자와 s2의 j번째 문자를 비교하고 다르다면 dp[i][j] = max(dp[i-1][j] , dp[i][j-1]) 이다. → i번째 문자와 j번째 문자가 다르기 때문에 직전 문자열에 각각 추가하여 비교한 최.. 2023. 2. 22. 이전 1 다음 반응형
