728x90
단계별로 풀어보기 동적계획법1의 14단계 문제 LCS
이번 학기 파이썬 수업에서 배웠던 거라 쉽게 풀 수 있었다.
public class Baek9251 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String n = in.next();
String m = in.next();
int[][] arr = new int[n.length() + 1][m.length() + 1];
for (int i = 0; i < n.length(); i++) {
for (int j = 0; j < m.length(); j++) {
if (i == 0 || j == 0) {
arr[i][j] = 0;
}
if (n.charAt(i) == m.charAt(j)) {
arr[i + 1][j + 1] = arr[i][j] + 1;
}
else {
arr[i + 1][j + 1] = Integer.max(arr[i][j + 1], arr[i + 1][j]);
}
}
}
System.out.println(arr[n.length()][m.length()]);
}
}
728x90
'알고리즘 문제' 카테고리의 다른 글
[백준] 14502번 연구소 (0) | 2020.01.05 |
---|---|
[백준] 12865 평범한 배낭 (0) | 2020.01.05 |
[백준] 1904번 01타일 (0) | 2020.01.04 |
[백준] 1003번 피보나치 함수 (0) | 2020.01.04 |
[백준] 1436번 영화감독 숌 (0) | 2020.01.04 |