[C++] 백준 1120번:문자열(브루트포스 알고리즘)

문제링크

1120번: 문자열

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

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

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

 

풀이

B에서 A와 차이가 가장 적은 위치를 찾고 왼쪽, 오른쪽으로 같은 문자를 붙여가며 A의 길이를 늘려주면 된다.

 

코드

#include <iostream>
#include <string>
using namespace std;
 
string A, B;
int ans;
 
int main() {
    cin >> A >> B;
 
    int max = 0;    // 같은 문자의 수 최대
    for (int i = 0; i <= B.size() - A.size(); i++) {
        int tmp = 0;
        for (int j = 0; j < A.size(); j++) {
            if (A[j] == B[i + j]) {
                tmp++;
            }
        }
        if (tmp > max) {
            max = tmp;
        }
    }
 
    cout << A.size()-max << endl;
    
}

 

메모

같은 알고리즘을 사용하는 다른 문제입니다. 필요하신 분은 보셔도 좋을 것 같습니다.

[C++] 백준 2422번:한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (브루트포스 알고리즘)