[백준/BOJ] 백준 20542번 : 받아쓰기

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

20542번: 받아쓰기

 

2차원 배열 cache에 cache[답안의 확인 인덱스][정답의 확인 인덱스] = "해당 위치의 답안과 정답을 확인할 때, 최소 점수"를 저장하는 다이나믹 프로그래밍을 통해 문제를 해결했다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int n, m;
string input;
string answer;
vector<vector<int>> cache;

int solve(int index1, int index2) {

	//답안은 다 확인했는데, 정답은 아직 끝까지 매치되지 않았을때 -> 답안에 정답 문자 나머지 추가
	if (index1 == n && index2 < m) {
		return m - index2;
	}

	//정답은 다 매치되었는데, 답안은 아직 다 확인하지 않았을때 -> 답안의 나머지 삭제    
	if (index2 == m && index1 < n) {
		return n - index1;
	}

	//모두 다 매치 되었을때
	if (index1 == n && index2 == m) {
		return 0;
	}

	int& ret = cache[index1][index2];

	if (ret != -1) {
		return ret;
	}

	ret = 987654321;

	//현재 위치에서 제출한 답안과 정답이 매치될때
	if (input[index1] == answer[index2]) {
		ret = min(ret, solve(index1 + 1, index2 + 1));
	}
	else if (input[index1] == 'i' && (answer[index2] == 'j' || answer[index2] == 'l')) {
		ret = min(ret, solve(index1 + 1, index2 + 1));
	}
	else if (input[index1] == 'v' && answer[index2] == 'w') {
		ret = min(ret, solve(index1 + 1, index2 + 1));
	}

	//현재 위치에서 제출한 답안이 정답과 매치되지 않을때
	else {
		//해당 위치를 정답문자로 변환
		ret = min(ret, solve(index1 + 1, index2 + 1) + 1);

		//해당 위치 삭제
		ret = min(ret, solve(index1 + 1, index2) + 1);

		//해당 위치에 새로운 정답문자 추가
		ret = min(ret, solve(index1, index2 + 1) + 1);
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;
	cin >> input;
	cin >> answer;

	cache.resize(n + 5);
	for (int i = 0; i < cache.size(); i++) {
		cache[i].resize(m + 5);
	}

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


	int result = solve(0, 0);

	cout << result << "\n";


	return 0;
}