반응형

https://www.acmicpc.net/problem/9177

 

9177번: 단어 섞기

입력의 첫 번째 줄에는 1부터 1000까지의 양의 정수 하나가 주어지며 데이터 집합의 개수를 뜻한다. 각 데이터집합의 처리과정은 동일하다고 하자. 각 데이터집합에 대해, 세 개의 단어로 이루어

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp[ 201 ][ 201 ]을 선언하고 -1로 초기화합니다.

 

2. a, b, c 문자열을 입력받고, a[ i + 1 ] == c[ i + j + 1 ] 일 때 dfs(i + 1, j), b[ j + 1 ] == c[ i + j + 1 ] 일 때 dfs(i, j + 1)를 통해 만들 수 있는 문자열인지 체크합니다.

 

3. dfs(0, 0)이 1이라면 yes를 아니라면 no를 출력합니다.

 

[ 소스코드 ]

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
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<string>
 
using namespace std;
 
int N;
int dp[201][201];
string a, b, c;
 
int dfs(int i, int j)
{
    if (i + j == c.size() - 1) return 1;
     if (dp[i][j] != -1) return dp[i][j];
    int& ret = dp[i][j];
    ret = 0;
 
    if (a[i + 1] == c[i + j + 1]) {
        ret = max(ret, dfs(i + 1, j));
    }
    
    if (b[j + 1] == c[i + j + 1]) {
        ret = max(ret, dfs(i, j + 1));
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for(int t = 1;t<=N;t++){
        cin >> a >> b >> c;
 
        a = ' ' + a;
        b = ' ' + b;
        c = ' ' + c;
 
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++) {
                dp[i][j] = -1;
            }
        }
 
        cout << "Data set " << t << ": ";
 
        if (dfs(0, 0)) {
            cout << "yes";
        }
        else {
            cout << "no";
        }
 
        cout<<'\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2174번 - 로봇 시뮬레이션 (C++)  (0) 2023.10.01
[ 백준 ] 14719번 - 빗물 (C++)  (0) 2023.09.30
[ 백준 ] 1351번 - 무한 수열 (C++)  (0) 2023.09.28
[ 백준 ] 14925번 - 목장 건설하기 (C++)  (0) 2023.09.27
[ 백준 ] 20924번 - 트리의 기둥과 가지 (C++)  (0) 2023.09.26

+ Recent posts

티스토리툴바