20542번. 받아쓰기

아이디어

'taken' 이라는 답안을 'fishcake' 라는 정답으로 바꾸는 과정은

'take' 를 'fishcake' 로 만드는 과정에 마지막 'n' 을 삭제하는 작업이 1번 더해진 것이라고 볼 수 있다.

 

'piza' 라는 답안을 'pizzaa' 라는 정답으로 바꾸는 과정은

'piza' 를 'pizza' 로 만드는 과정에 마지막 'a' 를 추가하는 작업이 1번 더해진 것이라고 볼 수 있다.

 

'johnber' 라는 답안을 'johnson' 이라는 정답으로 바꾸는 과정은

'johnbe' 를 'johnso' 으로 만드는 과정에 마지막 'r'을 'n' 으로 바꾸는 작업이 1번 더해진 것이라고 볼 수 있다.

 

이를 통해 dp[i][j] 를 답안의 i 번째 문자까지, 정답의 j 번째 문자까지 고려했을 때의 수정횟수라고 한다면 아래와 같은 점화식을 세울 수 있다.

 

dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1

 

다만 i 번째 문자와 j 번째 문자가 같은 경우 아무런 작업을 하지 않아도 되므로 이 때는

 

dp[i][j] = dp[i - 1][j - 1]

 

 

풀이코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= m; j++) {
            dp[0][j] = j;
        }

        String input = br.readLine();
        String answer = br.readLine();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char c1 = input.charAt(i - 1);
                char c2 = answer.charAt(j - 1);

                if (c1 == c2 || (c1 == 'i' && (c2 == 'j' || c2 == 'l')) || (c1 == 'v' && c2 == 'w')) {
                    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[n][m]);
    }
}