[C++] 백준 20542 받아쓰기

문제 링크

---

www.acmicpc.net/problem/20542

20542번: 받아쓰기

 

 

접근 방법

---

처음에 어떤 알고리즘을 적용해야 할지 몰라 문제를 못풀었습니다. 하지만 편집거리라는 알고리즘을 알고있다면 어렵지 않게 풀 수 있는 문제였습니다.

 편집거리 알고리즘은 LCS와 동작이 거의 비슷합니다. 하지만 차이점이 있다면 LCS는 일치하는 가장 긴 문자열을 찾아내기 위해 서로 일치하는 경우를 찾아 최댓값으로 갱신하였고, 편집거리는 가장 조금 수정하는 경우를 찾아내기 위해 서로 일치하지 않는 경우를 찾아 최소로 갱신한다는 차이가 있습니다.   

 

아래 블로그에 편집거리에 대한 자세한 설명이 있으니 참고 부탁드립니다.

hsp1116.tistory.com/41

편집 거리 알고리즘(Levenshtein Distance, Edit Distance)

 

문제에서 유의해야 될 사항은 한 가지가 있습니다.

답안의 한 철자를 char g, 정답의 한 철자를 char a하고 한다면 

 g가 'i'일 때, a가 'i','j','l'이라면 정답처리를 하고,

 g가 'v'일 때, a가 'v','w'라면 정답처리를 한다는 것입니다.

 

즉, 편집거리 알고리즘을 진행하며 같은지 다른지에 대한 비교연산을 위와 같이 정의해서 풀어나가 문제를 해결할 수 있었습니다.

 

 

소스 코드

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int N, M;

string guess;
string ans;

bool isCorrect(char g, char a) {
	if (g == a)
		return true;
	else if (g == 'i' && (a == 'i' || a == 'j' || a == 'l'))
		return true;
	else if (g == 'v' && (a == 'v' || a == 'w'))
		return true;
	else
		return false;
}

int editDistance() {

	vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0));

	for (int i = 1; i < N + 1; i++) //답안 
		dp[i][0] = i;
	for (int i = 1; i < M + 1; i++) //정답
		dp[0][i] = i;

	for (int i = 1; i < dp.size(); i++) { //답안
		for (int j = 1; j < dp[i].size(); j++) { //정답
			if (isCorrect(guess[i - 1], ans[j - 1])) //같다면 복제
				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; // 추가, 삭제, 수정 중 가장 적은 것
		}
	}
	return dp[N][M];
}

int main() {

	ios_base::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		char spell; cin >> spell;
		guess += spell;
	}
	for (int i = 0; i < M; i++) {
		char spell; cin >> spell;
		ans += spell;
	}
	cout << editDistance() << "\n";
}