백준 9251번 자바

문제

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

9251번: LCS

import java.util.Scanner;

public class Main9251 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		String n = sc.next();
		String k = sc.next();
		int[][] lcs = new int[n.length()+1][k.length()+1];
		
		for (int i=1; i<=n.length(); i++) {
			for (int j=1; j<=k.length(); j++) {
				if (n.charAt(i-1) == k.charAt(j-1)) {
					lcs[i][j] = lcs[i-1][j-1] + 1;
				} else {
					lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
				}
			}
		}
		System.out.println(lcs[n.length()][k.length()]);
	}
}

1. LCS라는 알고리즘을 처음 접해봤다. 알고리즘 그대로 문제를 푸는 것이라 어려움은 없었다. 다만 2차원 배열을 머릿속으로 그려보며 익숙해지도록 노력해야 한다.

 

2. LCS알고리즘

https://ahlight.tistory.com/59