백준 1120 문자열 python

A에 문자를 추가할 때 B 와 길이가 같을 때 까지만 추가하기 때문에 추가할 수 있는 글자수는 정해져있다. 이를 생각해서 풀면 될거 같다.

📜 문제 바로 가기 : 문자열

제출코드

파이썬

import sys
input = sys.stdin.readline

A, B = input().split()

diff = len(A)
for k in range(len(B) - len(A) + 1):
    cnt = 0
    for i in range(len(A)):
        if A[i] != B[i+k]:
            cnt += 1

    diff = min(diff, cnt)

print(diff) 

---

접근방법

앞뒤로 추가할 문자는 아무거나 추가할 수 있다.
그래서 어떤걸 추가할지 고민하지 말고 기존에 있는 문자부터 최적으로 맞춰놓기만 하면 되는 문제이다.

문제에서 준 예제 중 koder topcoder 이경우를 보자
이때 나올 수 있는 경우는 아래와 같다.

koder***
topcoder

*koder**
topcoder

**koder*
topcoder

***koder
topcoder

*에는 우리가 아무 문자열이나 넣을 수 있다.
즉 저 4가지 경우에서 차이가 가장 작은것이 문제가 요구하는 답이된다.