BOJ - 9251 ) LCS

 

---

 

https://www.acmicpc.net/problem/9251

9251번: LCS

---

최장 공통 부분 수열을 구하기 위해 이전까지의 최장 공통 부분 수열을 구해 놓는다.

 

현재 문자가 격자상 문자와 같으면 대각선의 값 + 1을 현재 값으로, 

 

다르다면 위 아래중 큰값으로 따라간다.

 

 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class LCS {

	public static void main(String[] args) throws Exception {
	
		BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
		String strA = br.readLine();
		String strB = br.readLine();
		int map[][] = new int[strA.length()+1][strB.length()+1];
		for(int i = 1 ; i < strA.length()+1 ; i++) {
			for(int j = 1 ; j < strB.length()+1 ; j++) {
				if(  strA.charAt(i-1) ==	 strB.charAt(j-1)  ) {
					map[i][j] = map[i-1][j-1]+1;
				} else {
					map[i][j] = max(map[i-1][j], map[i][j-1]);
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append(map[strA.length()][strB.length()] + "\n");
		System.out.println(sb);
	
	}

	private static int max(int i, int j) {
		return i = i > j ? i : j ;
	}
}

---