반응형
728x170
사실 이것은
정말 직관을 요하는 문제다.
브루트포스에 있지만.. 정말 브루트포스처럼 전수조사인지는 의문이다.
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분 보다보면 살짝씩 보인다.
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 1543번, 문서 검색 : C++ [CPP] (0) | 2021.12.05 |
---|---|
백준, BOJ, 2503번, 숫자야구 : C++ [CPP] (0) | 2021.12.05 |
백준, BOJ, 1937번, 욕심쟁이 판다 : C++ [CPP] *** (0) | 2021.12.01 |
백준, BOJ, 1194번, 달이 차오른다 가자 4 : C++ [CPP] ****** (0) | 2021.12.01 |
백준, BOJ, 16946번, 벽 부수고 이동하기 4 : C++ [CPP] (0) | 2021.11.30 |