[백준 1120] 문자열

[문제풀이]

문자열 A와 문자열 B가 주어졌을 때, 항상 A의 길이는 B의 길이보다 작거나 같은 조건에서 입력으로 주어졌을 때

A와 B의 길이가 같으면서도, A와 B의 차이를 최소가 되도록 하는 방법을 구하는 문제입니다.

 

채워 넣을 때는 아무거나 알파벳을 넣되 앞에서 넣나 뒤에서 넣나 최선의 방법으로 넣어야 우리는 최소의 경우를 구할 수 있습니다. 최선의 경우가 아니면 더 많은 방법으로 돌아가겠죠.

 

간단하게 주어진 입력에 대해서 비교를 하면 쉽습니다.

어처피 채워 넣는 건 최선의 방법으로 채워 넣기 때문에 기존에 입력된 부분의 차이만 구하면 그 차이가 바로 최소의 차이이기 때문입니다.

 

A : adaabc

B : aababbc

 

어릴 때 모양이 여러 조각 난 판이 있을 때 그 모양에 끼워넣기 위해서 이리저리 놓아서 넣는 경험을 해본 적이 있을 겁니다. 이를 똑같이 문제에 적용하면 B라는 판에 A라는 조각을 이리저리 끼워 넣어 보고 차이를 구하면 됩니다.

 

aababbc

adaabc

이렇게 끼워 넣어 보면 3군데가 차이가 됩니다.

 

그러면 다른 방법으로 끼워봅시다. (약간 삐뚤긴 했지만.. 잘 보면 2군데가 차이가 됩니다.)

aababbc

  adaabc

 

어떤가요? 2군데 차이를 기준으로 채워 넣는 건 최선의 방법으로 넣으니까 결국 답은 2라는 것을 알 수 있습니다.

정리하면 B라는 문자열에 A라는 작은 문자열을 이리저리 껴놓고 틀린 차이만 카운팅 해서 최소한으로 갱신해주면 문제를 해결할 수 있게 됩니다.

 

더 있을까요?

아닙니다. A라는 문자열을 저희가 늘리거나 줄일 수 있는 방법이 없기 때문에 총 2가지 케이스에 대해서만 생각할 수 있습니다.

 

이를 어떻게 구현할까요?

되도록이면 일단 해보고 그래도 모르겠다면 아래의 풀이를 봐주시면 좋겠습니다.

이런 문제가 약간 실력의 향상의 밑거름이라고 생각되는 좋은 문제입니다!

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	string a, b;
	cin >> a >> b;
	int ans = b.size();
	int len = b.size() - a.size();
	for (int i = 0; i <= len; i++)
	{
		int cnt = 0;
		for (int j = 0; j < a.size(); j++)
		{
			if (a[j] != b[i + j])
				cnt++;
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}