백준 1120번 - 문자열

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

문제 분류는 그리디 문제로 백준에 나와 있지만

그냥 2중 for문으로 풀면 된다.

포인트는 A가 B보다 길이가 작거나 같고 다른 부분은 추가가 된다는 부분이다.

이때, A의 첫 문자를 B의 어떤 지점부터 비교해서 시작할 때 가장 값이 작은지를 구하면 된다.

즉 

A가 "abc"이고

B가 "abcdef" 일 때

A[0]을 B[0]부터 비교하면 모두 같고 B[3]부터 B[5]는 def로 채우면 된다.

A[0]을 B[1]부터 비교하면 모두 다르고 B[0]과 B[4],B[5]는 각각 a,e,f로 채우면 된다.

이런 식으로 접근하면 A[0]부터 A[2]를 

B[0]부터 B[2]까지 비교하고

...

B[B의 문자열 길이 - A의 문자열길이] 부터 B[B의 문자열 길이 - A의 문자열길이 + A의 문자열길이] 까지 비교하면 된다

쉬운 문제를 너무 어렵게 설명한 것 같은데

코드를 보면 바로 이해할 수 있다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main(){
    
    string A,B;
    cin>>A>>B;
    
    int ans=50; //A와 B의 문자가 모두 다른 경우
    
    for(int dist=0;dist<=B.length()-A.length();dist++){
        
        int cnt=0;
        for(int i=0;i<A.length();i++){
            if(A[i]!=B[i+dist])
                cnt++;
        }
        
        ans=min(ans,cnt);
    }
    cout<<ans<<endl;
    
    return 0;
}