1120.문자열

(*)이번에 풀어볼 문제는 백준의 1120번 문자열이다.

A문자열은 B의 문자열보다 짧고 A문자열에는 문자열 앞과 뒤에 문자를 추가하는 두 가지 연산이 가능하다

이러한 연산은 B와 길이가 같아질 때까지 가능하고 추가해서 길이를 같게만든 문자열 A와 B의 차이를

최소화 시킬 수 있는 차이를 구하면된다.

1120번: 문자열

이 문제에는 함정이 있다. 곰곰히 생각해보면 피할 수 있다. -> 이래서 문제풀기전에 생각하는 시간이 가장 중요하다.

문제에서 주어진 연산은 앞과 뒤에 문자를 붙일 수 있는데 이는 애초에 구현한 필요도 없다.

-> 앞과 뒤에 붙이는 문자는 어처피 내맘이므로 무조건 같게 만들 수 있다.

 

그러므로 위의 그림처럼 나머지 A문자열을 자리를 옮겨가며 B의 문자열과 차이를 비교하면 끝난다.

 

 

< Code 설명 >

#include <iostream>
#include <string>

using namespace std;

#define MAX 50

int main() {
	string A, B;
	cin >> A >> B;
	int cnt = B.length() - A.length(); //두 문자열의 길이차이

	int min = 9999999;
	int count = 0;
	for (int i = 0; i <= cnt; i++){ // A문자열이 옮길 수 있는 길이
		for (int j = i; j < A.length()+i; j++){ // A문자열의 길이까지만
			if (A[j-i] != B[j]) // A문자열은 그대로지만 비교대상은 옮겨짐
				count++; // 다르면 카운트!
		}
		if (min > count) // 구한 차이중의 최소값을 저장
			min = count;
		count = 0;
	}
	cout << min << endl;
	return 0;
}