Q9251. LCS

String을 비교하며 최대값을 저장하며 나아가는 로직

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q9251 { static int[][] dp; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); String firstString = st.nextToken(); st = new StringTokenizer(br.readLine()); String secondString = st.nextToken(); dp = new int[firstString.length()+1][secondString.length()+1]; for (int i = 1; i <= firstString.length(); i++) { int yChar = firstString.charAt(i-1); for (int j = 1; j <= secondString.length(); j++) { int xChar = secondString.charAt(j-1); if (yChar == xChar) { dp[i][j] = dp[i-1][j-1]+1; } else { dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } } System.out.println(dp[firstString.length()][secondString.length()]); } }