9177번: 단어 섞기
세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는
www.acmicpc.net
str1 : 첫 번째 단어
str2 : 두 번째 단어
result : 세 번째 단어
dp[idx1][idx2] : 현재 확인하려는 알파벳이 str1[idx1], str2[idx2]일 때 result를 만들 수 있는지 여부
재귀를 통해 두 단어와 세 번째 단어를 비교할 인덱스(idx1, idx2, idx)를 넘겨줍니다.
str1[idx1] == result[idx]이면 첫 번째 단어와 세 번째 단어의 인덱스를 1 증가(idx1 + 1, idx2, idx + 1)
str2[idx2] == result[idx]이면 두 번째 단어와 세 번째 단어의 인덱스를 1 증가(idx1, idx2 + 1, idx + 1)
를 확인해줍니다.
인덱스의 조합이 중복으로 나오기때문에 시간적 손해를 줄이기위해 dp를 사용하였습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <iostream>
#include <string>
#include <cstring>
#define max(a, b) {a > b ? a : b}
using namespace std;
string str1, str2, result;
int dp[201][201];
int size1, size2, rsize;
int func(int idx1, int idx2, int idx) {
if (idx == rsize) return 1;
int &ret = dp[idx1][idx2];
if (ret != -1) return ret;
ret = 0;
if (idx1 < size1 && str1[idx1] == result[idx]) ret = func(idx1 + 1, idx2, idx + 1);
if (idx2 < size2 && str2[idx2] == result[idx]) ret = max(ret, func(idx1, idx2 + 1, idx + 1));
return ret;
}
void input() {
cin >> str1 >> str2 >> result;
size1 = str1.size();
size2 = str2.size();
rsize = result.size();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int tc;
cin >> tc;
for (int t = 1; t <= tc; t++) {
memset(dp, -1, sizeof(dp));
cout << "Data set " << t << ": ";
input();
if (func(0, 0, 0)) cout << "yes\n";
else cout << "no\n";
}
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 2228 구간 나누기 (0) | 2021.03.21 |
|---|---|
| boj 1695 팰린드롬 만들기 (0) | 2021.03.20 |
| boj 10942 팰린드롬? (0) | 2021.03.12 |
| boj 17404 RGB거리 2 (0) | 2021.02.28 |
| boj 2616 소형기관차 (0) | 2021.02.27 |