[BOJ] 1120번: 문자열

문제링크: 백준/BOJ https://www.acmicpc.net/problem/1120

1120번: 문자열

 처음에는 b에 맞춰서 a를 하나하나 만들어 봐야 하나 생각해서 문제가 너무 꼴 보기 싫었었다.

하지만 문제가 그리디에 분류되어 있는걸 보고 문제 조건을 차분하게 다시 읽어보니 방법이 떠올랐다.

 

예시를 들어서 설명해보겠다.

문자열 A : abcd

문자열 B : faecgi

 

우리의 임무는 A의 양끝에 문자열을 자유롭게 추가해서 B와의 차이가 최소가 되게 만들어야 함이다.

그러면 B를 A의 문자열 개수만큼의 부분문자열들로 쪼개어 생각하면 어떨까?

A와의 차이가 최소가 되는 B의 부분문자열만 찾으면 A의 양끝은 B의 부분문자열의 양끝과 똑같이 덧붙여 주면 되기 때문이다.

설명이 부족한 것 같아 그림을 그려보았다.

 

 

 

이 경우 A와 B의 부분문자열의 차이는 4이다. 따라서 A에 오른쪽 끝에 B와 같이 g i 를 추가해주면 차이는 4이다.

 

 

 

 

이 경우에는 A와 B의 부분문자열의 차이는 2이다. 따라서 A의 양 끝에 B와 같이 f와 i를 각각 추가해주면 차이는 2이다.

첫번 째 경우보다 차이가 적으므로 답을 갱신해줘야 한다.

 

 

 

 

이 경우에는 A와 B의 부분문자열의 차이가 4이므로 마찬가지로 A의 왼쪽 끝에 f와 a를 추가해주면 차이가 4이다.

 

B의 모든 부분문자열에 대해 A와의 차이를 구한 후 최솟값을 답으로 찾으면 된다.

아래는 그것을 구현한 코드이다.

 

 

 

/*
Baekjoon 1120번: 문자열
*/
#include <iostream>
#include <string>
using namespace std;

char arr[50];
int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	string a, b;
	cin >> a >> b;

	int aLen = a.size(), bLen = b.size(), min = aLen;
	for (int i = 0; i <= bLen - aLen; ++i) {
		int tmp = 0;
		for (int j = 0; j < aLen; ++j) {
			if (a[j] != b[i + j]) tmp++;
		}
		if (min > tmp) min = tmp;
	}

	cout << min;
}