알고리즘
백준 1099번 알 수 없는 문장 C++
영춘권의달인
2022. 2. 16. 13:52
1. 문장을 순회하면서 각각의 단어마다 현재 인덱스 - 단어의 크기 + 1 부터 현재 인덱스까지의 구성된 문자가 단어와 같은지 확인한다.
ex) 현재 인덱스가 2이고, 단어가 "one" 이라고 하면 2 - 3 + 1 = 0 부터 2 까지 구성된 문자는 n, e, o 이고 이는 "one"과 구성된 문자가 같다.
2. 1에서 구한 인덱스 - 단어의 크기 + 1 이 0보다 작거나 구성된 문자가 같지 않다면 다음 문자를 검색한다.
1에서 구성된 문자가 같다면 순서를 바꾸는 비용을 구하고 dp로 해결할 수 있다.
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
using namespace std;
using ll = long long;
bool operator==(const map<char, int>& lhs, const map<char, int>& rhs) {
if (lhs.size() != rhs.size()) return false;
auto it1 = lhs.begin();
auto it2 = rhs.begin();
bool ret = true;
while (true) {
if (it1 == lhs.end() || it2 == rhs.end()) break;
if (it1->first == it2->first && it1->second == it2->second) {
++it1;
++it2;
}
else {
ret = false;
break;
}
}
return ret;
}
int GetPrice(const string& comp, const string& target) {
int ret = 0;
for (int i = 0; i < comp.length(); i++) {
if (comp[i] != target[i]) ret++;
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string target;
cin >> target;
int n;
cin >> n;
vector<string> v(n);
vector<map<char, int>> m(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
for (int j = 0; j < v[i].length(); j++) {
m[i][v[i][j]]++;
}
}
vector<int> dp(target.length(), -1);
for (int i = 0; i < target.length(); i++) {
for (int j = 0; j < n; j++) {
int start = i - v[j].length() + 1;
if (start < 0) continue;
map<char, int> tmp_map;
for (int k = start; k <= i; k++) {
tmp_map[target[k]]++;
}
if (m[j] == tmp_map) {
int price = GetPrice(target.substr(start, v[j].length()), v[j]);
if (start == 0) {
if (dp[i] == -1) dp[i] = price;
else dp[i] = min(dp[i], price);
}
else {
if (dp[start - 1] == -1) continue;
else {
if (dp[i] == -1) dp[i] = dp[start - 1] + price;
else dp[i] = min(dp[i], dp[start - 1] + price);
}
}
}
}
}
cout << dp[target.length() - 1];
};