[백준] 1120 문자열 - 완전탐색

www.acmicpc.net/problem/1120

1120번: 문자열

문제만 이해하면 쉽게 풀 수 있는 완탐 문제

길이가 작은 문자열 A 가 문자열 B에 위치했을때, 가장 많이 중첩된 문자의 갯수를 구하면 바로 문제 해결!

문자열 앞뒤로 문자를 추가 할 수 있어서, 길이가 차이나는 만큼은 문자의 차이 없이 원하는 문자로 채울 수 있다.

따라서 A 문자열이 B문자열에 문자가 가장 많이 중첩되는 곳을 찾고, A문자열 사이에 문자를 넣을 수 없으니 그 때의 중첩되지 않은 차이를 출력해주면 정답이 나온다.

 

int main() {
	
	string A, B;
	int maxnum = 0;
	cin >> A >> B;
	int cnt;
	for (int i = 0; i <= B.length()-A.length(); i++) {
		cnt = 0;
		for (int k = 0; k < A.length(); k++) {
			
			if (A[k] == B[i+k])cnt++;
		}
		
		maxnum = max(maxnum, cnt);
	}
	int answer = A.length() - maxnum;
	cout << answer;
	
	return 0;
}

 

문제의 Test Case로 치면 , 최대한 문자열을 중첩시켜 위치하면 cnt값이 4가 나오고 A문자열 길이가 6이므로

6 - 4 = 2가 최소 차이가 된다.