백준, BOJ, 1120번, 문자열 : C++ [CPP]

사실 이것은

정말 직관을 요하는 문제다.

 

브루트포스에 있지만.. 정말 브루트포스처럼 전수조사인지는 의문이다.

 

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

 

---

 

#맞는 풀이

#include <iostream>
#include <string>
#include <climits>
#include <algorithm>


using namespace std;

int main(){
    string a;
    string b;
    
    cin >> a >> b;
    
    int lengthA = a.size();
    int lengthB = b.size();
    
    int numToAdd = lengthB-lengthA;
    
    
    int m = INT_MAX; // 최솟값
    
    
    
    //lengthA에 대해서 lengthB의 어느 부분이랑 가장 매치가 되는지
    //-> 가장 맞는 부분을 구한다면 해당 부분에서의 차이가 곧 전체의 차이임
    // 왜냐하면 앞, 뒤에 빈 것은 알맞게 채우면 되니까.
    for(int i = 0; i<numToAdd + 1; i++){
        int cnt = 0;
        
        for(int j = 0; j<lengthA; j++){
            if(a[j] != b[i+j]){
                cnt++;
            }
        }
        
        m = min(cnt, m);
        
    }
    
    
    cout << m ;
    
    
    return 0;
}

 

 

즉, B와 가장 차이가 없는 문자열을 생성해야한다.

즉, B와 일치율이 높아야 한다.

일치율은 같은 자리에 같은 문자가 있어야 한다.

 

그러나 A에는 아무문자나 추가시킬 수 있으므로..

B에 있는 그대로를 추가시키면 좋겠다.

 

그렇다면.. 어떻게 해야하는가??

 

B에서 A와 가장 유사한 부분을 찾는다.

 

A = bfd 

B = abcde라 치면

 

앞에는 a

뒤에는 e

를 추가시키면 될 것 같다.

실제로 모든 문자를 대입해보는 것보다는..

 

bfd를 기준으로 어차피 붙일건데..

bfd가 b의 어느부분과 가장 유사하느냐?

 

bcd부분이 bfd와 가장 유사하다. 차이는 1개밖에 없다.

즉, bfd에서 앞 뒤로 b에 알맞게 추가하면 된다.

 

그래서 직관적으로 이게 보이지 않는 이상 못푼다.

10분 보다보면 살짝씩 보인다.