https://www.acmicpc.net/problem/1120
시간 2초, 메모리 128MB

input :

• A B (1 <= len(A), len(B) <= 50)

output :

• A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력

조건 :

• 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수

• A의 길이는 B의 길이보다 작거나 같다.

• 다음과 같은 연산을 할 수 있다.

• A의 앞에 아무 알파벳이나 추가한다.

• A의 뒤에 아무 알파벳이나 추가한다.

---

틀렸다고 기록을 해뒀던 문제인데 해결은 했었다. 오늘은 이에 대한 풀이를 다시 기억하는 의미에서 작성을 하려 한다.

다음 풀이

1. A는 언제나 B보다 길이가 작다.
2. 최대 길이는 49, 50이다.
3. 아무 알파벳?

A를 B에다가 맞춰볼 수 있다. 가장 차이가 적은 부분을 찾을 수 있다.
최대 길이를 통해 한 25, 50의 길이를 가졌다고 쳤을 떄. 25 * 25의 연산이면 충분하다고 생각할 수 있다.
차이가 적은 부분을 찾았다면, 그 외의 부분은 동일하다고 가정할 수 있다.(아무 알파벳이나 넣기 때문에)

고로 완전탐색을 통해 A를 B에다가 대입을 하며 차이가 가장 작은 부분을 찾는다.

import sys

a, b = sys.stdin.readline().split()

ans = float('inf')
for i in range(len(b) - len(a) + 1):
    cnt = 0

    for j in range(len(a)):
        if a[j] != b[i + j]:
            cnt += 1

    ans = min(ans, cnt)

print(ans)