[백준 알고리즘 풀이] 2216번 문자열과 점수

Sequence Alignment에서 잘 알려진 문제로 edit distance 계산하라는 문제다. 위키피디아에 잘 정리되있기 때문에 구체 설명은 하지 않는다. https://en.wikipedia.org/wiki/Edit_distance

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();
  }
 
}