[BOJ 1120]문자열

문제출처

https://www.acmicpc.net/problem/1120

처음에는 x문자열과 y문자열을 최대한 맞춰가면서 풀이해야 한다고 생각해서 많이 어려움을 느꼈다.

하지만 결국 앞이던 뒤던 y문자열과 비슷한 최적의 경우를 찾는 것이기 때문에 구현 대상에서 제외하고

x문자열과 y문자열의 차이값을 찾아가면서 구현했다.

예를 들어 설명하면 다음과 같다.

x가 adaabc

y가 aababbc 인경우를 생각해보면 문자열의 길이 차이는 1만큼 난다.

이때, y[0]부터 y[5]까지와 x를 비교해서 차이값, y[1]부터 y[6]까지와 x를 비교해서 차이값의 최솟값을 출력해주면 되는 문제이다.

소스코드

#include <iostream>
#include <string>
#define MAX 987654321
using namespace std;
int min(int a, int b) {
    return a>=b ? b : a;
}
int main(int argc, char** argv) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string x,y;
    int ans=MAX;
    cin>>x>>y;
    for (int i=0; i<= y.size() - x.size(); i++) {
        int cnt = 0;
        int yIdx=i;
        for (int j=0; j < x.size(); j++, yIdx++) {
            if (x[j] == y[yIdx]) continue;
            cnt++;
        }
        ans = min(ans, cnt);
    }
    cout<<ans;
    return 0;
}