[BOJ] 백준 9251 - LCS 풀이

1. 문제

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

9251번: LCS

2. 풀이 Point

• 두 문자열을 입력 받아서 표를 그려보았다.
• 표의 값은 맨 앞에서부터 탐색하는 지점까지 문자열을 비교하여 최대 몇 개가 겹치는지를 적었다.
• 예를 들어, 그림의 파란색의 경우 CA와 A를 비교한다. 이때는 최대 겹치는 구간이 A 하나이므로 1을 적는다.
• 그림의 초록색의 경우 CAPC와 AC를 비교한다. 이때는 최대 겹치는 구간이 AC 이므로 2를 적는다.
• 이 표를 그리다 보니 다음과 같은 규칙을 발견할 수 있었다.
  • (1) 탐색하고 있는 지점( 각 문자열의 끝 지점)이 같을 경우
    • 끝 지점이 같다면, 같은 지점이 나오기 전까지의 값 + 1
  • (2) 탐색하고 있는 지점( 각 문자열의 끝 지점)이 다를 경우
    • 끝 지점이 다르다면, 탐색하고자 하는 위치의 행 - 1, 탐색하고자 하는 위치의 열 - 1 중 최대값
• 이를 식으로 만든다면
  • dp[i][j] = dp[i - 1][j - 1] + 1;
  • dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    
    
    

3. Error Point

• 첫 번째, 두 번째 입력 문자열을 받아서 Length를 구한다. Why?? ⇒ 두 문자열의 길이가 다를 수도 있기 때문!!
• i - 1, j - 1을 하기 때문에 dp 배열의 사이즈를 +1씩 해준다.
  
  
  

4. 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	    String first = br.readLine();
	    String second = br.readLine();
	    
			// 두 문자열의 길이를 체크
	    int sizeFirst = first.length();
	    int sizeSecond = second.length();
	
			// dp 배열의 사이즈를 하나씩 증가시켜줘야한다.
	    int[][] dp = new int[sizeFirst + 1][sizeSecond + 1];
	
	    for (int i = 1; i <= sizeFirst; i++) {
	        for (int j = 1; j <= sizeSecond; j++) {
	        	if (first.charAt(i - 1) == second.charAt(j - 1)) {  // 끝 문자열이 같을 경우
	        		dp[i][j] = dp[i - 1][j - 1] + 1;
	        	} else {
	        		dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);  // 끝 문자열이 다를 경우
	        	}
	        }
	    }
	    
      bw.write(Integer.toString(dp[sizeFirst][sizeSecond]));
      bw.flush();
      bw.close();
      br.close();
    }
}

5. 점수

70/100