백준 1120번: 문자열

[문제 링크]

1120번: 문자열

---

이 문제가 왜 그리디 알고리즘으로 분류되어있는지 아리송한 문제였다.

필자는 완전탐색으로 풀이했다고 생각한다.

 

A문자열이 B문자열보다 짧을 경우 문자열 앞뒤로 아무 알파벳을 추가할 수 있다는 것은 B문자열과 일치하는 문자들을 추가할 수 있다는 뜻이기 때문에 A, B 문자열의 길이 차이만큼 한 칸씩 밀어서 비교하여 그중 차이가 최소인 값을 찾으면 그 값이 정답이 된다.

---

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

const int INF = 987654321;
int min(int a, int b) { return a < b ? a : b; }

int Greedy(string& a, string& b)
{
	int aLen = a.length();
	int bLen = b.length();
	int diff = bLen - aLen;


	int ret = INF;

	for (int i = 0; i <= diff; i++)
	{
		int res = 0;
		for (int j = 0; j < aLen; j++)
			if (a[j] != b[i + j])
				res++;

		ret = min(ret, res);
	}

	return ret;
}

int main(void)
{
	string A, B;
	cin >> A >> B;

	cout << Greedy(A, B) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 111 day