[BOJ/백준][Gold4] 15483 : 최소 편집 (C++)

https://www.acmicpc.net/problem/15483

15483번: 최소 편집

 

[난이도] Gold4
[유형] DP

[풀이]
기본 LCS를 변경한 DP로 풀 수 있다.

DP[i][j] : 바꿔야할 문자열이 a, 목표 문자열이 b일때 a[1...i],b[1...j]까지의 a,b에 대한 최소 편집 개수
a[i]==b[j] 이면 DP[i][j] = DP[i-1][j-1] 이며
아닌 경우 DP[i-1][j-1] , DP[i-1][j] , DP[i][j-1] 중 최솟값에 1을 더한 값이 된다.
DP[i-1][j-1]인 경우는 a[i]를 b[j]로 바꾸는 연산, DP[i-1][j],DP[i][j-1]인 경우는 문자 하나를 추가하는 연산이다.

 

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
string a,b,c;
int dp[1001][1001];
int main(){
    cin >> a >> b;
    a='A'+a;
    b='B'+b;
    int n=a.size(), m=b.size();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i==0&&j==0) continue;
            if(i==0){
                dp[i][j]=j;
                continue;
            }
            if(j==0){
                dp[i][j]=i;
                continue;
            }
            if(a[i]==b[j]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
        }
    }
    cout << dp[n-1][m-1] << endl;;
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/15483.cpp