import java.util.Scanner; /* * 2216번 문자열과 점수 */ public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int match = sc.nextInt() * -1; int gap = sc.nextInt() * -1; int mismatch = sc.nextInt() * -1; sc.nextLine(); String a = sc.nextLine(); String b = sc.nextLine(); int[][] opt = new int[a.length() + 1][b.length() + 1]; for (int i = 1; i <= a.length(); i++) opt[i][0] = opt[i - 1][0] + gap; for (int j = 1; j <= b.length(); j++) opt[0][j] = opt[0][j - 1] + gap; for (int i = 1; i <= a.length(); i++) { for (int j = 1; j <= b.length(); j++) { int diag; if (a.charAt(i - 1) == b.charAt(j - 1)) { diag = opt[i - 1][j - 1] + match; } else { diag = opt[i - 1][j - 1] + mismatch; } opt[i][j] = Math.min( Math.min(opt[i - 1][j] + gap, opt[i][j - 1] + +gap), diag); } } System.out.println(opt[a.length()][b.length()] * -1); sc.close(); } }
[백준 알고리즘 풀이] 2216번 문자열과 점수
Sequence Alignment에서 잘 알려진 문제로 edit distance 계산하라는 문제다. 위키피디아에 잘 정리되있기 때문에 구체 설명은 하지 않는다.
https://en.wikipedia.org/wiki/Edit_distance
Subscribe to:
Post Comments (Atom)
-
음성 인공지능 분야에서 스타트업이 생각해볼 수 있는 전략은 아마 다음과 같이 3가지 정도가 있을 것이다: 독자적 Vertical 음성 인공지능 Application 구축 기 음성 플랫폼을 활용한 B2B2C 형태의 비지니스 구축 기 음성 플랫폼...
-
무한 집합의 크기 Cardinality , 즉 원소의 개수를 수학에서는 '농도'라고 말한다. 유한 집합의 크기는 그대로 원소의 개수 이지만, 무한 집합의 경우는 원소의 개수를 낱낱이 셈하는 것은 불가능하기 때문에 '농도'라...
-
In addressing the growing problem of junk email on the Internet, I examined methods for the automated construction of filters to eliminate s...
No comments:
Post a Comment