👀 문제
https://www.acmicpc.net/problem/9251
👊 도전
1. 설계
- 이차원배열을 만들어서 두 문자가 같으면 좌측 상단 값+1을, 다르다면 좌측 또는 상단의 값 중 최댓값을 선택한다.
- 마지막 배열 원소가 정답이다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;
/**
*
* @author HEESOO
*
*/
public class Main {
public static void main(String[] args){
Scanner input=new Scanner(System.in);
String str1=input.next();
String str2=input.next();
String[] s1=str1.split("");
String[] s2=str2.split("");
int[][] dp=new int[s1.length+1][s2.length+1];
for(int i=1;i<s1.length+1;i++){
for(int j=1;j<s2.length+1;j++){
if(s1[i-1].equals(s2[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]);
}
}
System.out.println(dp[s1.length][s2.length]);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- DP를 이용한다.
- 문자열 두 개를 입력받아 배열로 쪼갠다.
- 값 계산할 dp를 생성한다. 이때 길이는 두 문자열 배열 길이+1이다. +1을 하는 이유는 맨 앞에 0을 넣어 좌측 상단 값을 가져올 수 있게 하기 위함이다.
- 이중 for문으로 모든 문자를 비교하며 같으면 좌측 상단 값+1을, 다르다면 좌측 또는 상단의 최댓값을 선택한다.
👏 해결 완료!
참고
- [백준][DP] 9251 LCS 알고리즘 https://118k.tistory.com/483