[boj] 최소 편집_15483JAVA

문제 캡처

소스 코드

import java.util.*;
import java.io.*;

public class 최소편집_15483 {
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String A = bf.readLine();
		String B = bf.readLine();
		int[][] dp = new int[A.length()+1][B.length()+1];

		for (int i = 0; i < dp.length; i++) {
			dp[i][0] = i;
		}
		for (int i = 0; i < dp[0].length; i++) {
			dp[0][i] = i;
		}
		
		for (int i = 1; i < A.length()+1; i++) {
			for (int j = 1; j < B.length()+1; j++) {
				if(A.charAt(i-1) == B.charAt(j-1)) {
					dp[i][j] = dp[i-1][j-1];
				}else {
					dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]),dp[i-1][j-1])+1;					
				}
			}
		}
		
		System.out.println(dp[A.length()][B.length()]);

	}
}	

Comment…💭

• 전형적인 DP문제,,각 자리에 알파벳을 비교하며 같으면 직전 알파벳 비교한것과 같은값으로, 아니라면 추가(dp[i][j-1]), 삭제(dp[i-1][j]), 교체(dp[i-1][j-1]) 한 값 중 가장 작은 값 선택 후 횟수 +1 하기!