원본 문자열 $S$와 만들려는 문자열 $P$가 주어진다.
$S$의 부분 문자열을 복사해서 $P$를 만들 수 있을 때 이 연산의 최솟값을 구하는 문제이다.
처음에는 2차원으로 구간 [l, r]을 쪼개듯이 dp로 돌려서 풀긴했는데 거의 2초가까이 나왔다.
이 문제는 1차원으로 충분히 풀 수 있다.
밑의 소스는 300ms정도 나온 소스이다.
find 함수를 이용해서 그런지 최적의 소스와 시간차이가 좀 난다.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
#define INF 987654321
string A, B;
int N, M;
int dp[1001];
int solve(int idx) {
if (idx == M) return 0;
int &ret = dp[idx];
if (ret != -1)return ret;
ret = INF;
for (int next = idx;next < M;next++) {
if (A.find(B.substr(idx, next - idx + 1)) != string::npos)
ret = min(ret, solve(next + 1) + 1);
}
return ret;
}
int main() {
memset(dp, -1, sizeof dp);
ios::sync_with_stdio(false);
cin >> A >> B;
N = A.length(), M = B.length();
cout << solve(0);
return 0;
}
| cs |
원본 문자열을 기준으로 반복문을 돌리면 위와같이 find함수를 사용하지 않고 $O(N)$만에
해결할 수 있다.
(find함수 자체로만 $O(N^2)$정도 소모되는듯 하다.)
맨 처음에 풀때처럼 최적의 방법이 생각이 나지 않는다면 발상을 바꿔서 거꾸로 생각해보도록하자.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
#define INF 987654321
string A, B;
int N, M;
int dp[1001];
int solve(int idx) {
if (idx == M) return 0;
int &ret = dp[idx];
if (ret != -1)return ret;
ret = INF;
for (int n = 0;n < N;n++) {
if (A[n] != B[idx]) continue;
int cnt = 0;
while (n + cnt < N && idx + cnt < M && A[n + cnt] == B[idx + cnt]) cnt++;
ret = min(ret, solve(idx + cnt) + 1);
}
return ret;
}
int main() {
memset(dp, -1, sizeof dp);
ios::sync_with_stdio(false);
cin >> A >> B;
N = A.length(), M = B.length();
cout << solve(0);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기