[백준/C++] 9177번: 단어 섞기(G4)

문제

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

9177번: 단어 섞기

 

 

 

사용한 알고리즘

2022.01.19 - [PS/Algorithm] - [알고리즘 개념정리] 3. 동적계획법(DP)

 

 

풀이

세 개의 단어를 각각 A, B, C라고 하자.

dp[i][j] 에는
A의 i-1까지, B의 j-1까지 사용해서 C의 i+j-1까지 만들 수 있다면 1, 없다면 0을 담았다.
기저조건은 dp[0][0]=1이다.

 

 

A="cat", B="tree", C="tcraete"인 경우를 생각해보자.

dp table	' '	t	r	e	e
' '	1	1	0	0	0
c	0	1	1	0	0
a	0	0	1	1	0
t	0	0	0	1	1

표의 1열과 1행을 채우는 방법은 간단하다.
1열을 채우는 방식으로 설명하자면,
현재 보고 있는 인덱스까지 A와 C가 같으면 dp를 1로 채우면 된다.
즉, A[i-1]==C[i-1] && dp[i-1][0]==1 이면 dp[i][0]=1 이다.

표의 내부를 채워보자.
현재 채우려는 칸의 위쪽 칸이 1이라면, 현재 인덱스의 A와 C가 같으면 dp가 1이다.
즉, A[i-1]==C[i+j-1] && dp[i-1][j] 이면 dp[i][j]=1 이다.
마찬가지로,  
현재 채우려는 칸의 아래쪽 칸이 1이라면, 현재 인덱스의 B와 C가 같으면 dp가 1이다.
즉, B[j-1]==C[i+j-1] && dp[i][j-1] 이면 dp[i][j]=1 이다.

 

소스코드

#include <iostream>
using namespace std;

int tc;
string A,B,C;
int alen, blen;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>tc;
    for(int n=1; n<=tc; n++){
        cin>>A>>B>>C;
        alen=A.length(), blen=B.length();
        // A의 i-1까지, B의 j-1까지 사용해서 C의 i+j-1까지 만들 수 있다면 1, 없다면 0
        int dp[201][201];
        for(int i=0; i<201; i++){ // dp배열 초기화
            for(int j=0; j<201; j++)
                dp[i][j]=0;
        }
        dp[0][0]=1; // 기저조건
        for(int i=1; i<=alen; i++){ // 1열 채우기
            // 현재글자 같고 앞에도 다 같았으면 1
            if(A[i-1]==C[i-1] && dp[i-1][0]) dp[i][0]=1;
        }
        for(int i=1; i<=blen; i++){ // 1행 채우기
            // 현재글자 같고 앞에도 다 같았으면 1
            if(B[i-1]==C[i-1] && dp[0][i-1]) dp[0][i]=1;
        }
        for(int i=1; i<=alen; i++){ // 내부 채우기
            for(int j=1; j<=blen; j++){
                if((dp[i-1][j] && A[i-1]==C[i+j-1]) || (dp[i][j-1] && B[j-1]==C[i+j-1]))
                    dp[i][j]=1;
            }
        }

        if(dp[alen][blen])
            cout<<"Data set "<<n<<": yes\n";
        else cout<<"Data set "<<n<<": no\n";
    }
    return 0;
}