발코딩 C++ - 백준 3257

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

DP 문제.

처음에는 그리디 접근했다가 시간을 많이 사용했다.

현재의 선택이 미래에 영향을 끼칠 수 있기 때문에 DP를 사용해야 한다.

비슷한 접근의 DP 문제와 비슷한 유형을 더 많이 풀어봐야 익숙해질 것 같다.

문제 접근

문자열의 길이의 최댓값이 150이다.

이는 문제 접근을 DP로 할 수 있다는 것을 암시한다.

입력 순서대로 문자열들을 $a,b,c$라고 하자.

$a="tata", b="mama",c="mtamataa"$라고 할 때,

$c[0]$은 $b$의 것이고 $c[1]$은 $a$의 것이다.

하지만 $c[2]=a$는 누구의 것으로 판명내기 어렵다.

따라서 "가능한" 모든 경우를 다 탐색해주어야 한다.

그리고 이를 DP 테이블에 기록하고,

가능한 경우를 역추적해 찾는다.

$DP(i,j)$를 $a$의 $i$번째, $b$의 $j$번째 문자열까지 확인했을 때,

내려야 하는 선택이라고 하면 다음과 같은 점화 관계가 성립한다.

$DP(i,j)=1$ if c[i+j]==a[i] && DP(i-1,j)가 가능한 경우
$DP(i,j)=2$ if c[i+j]==b[i] && DP(i,j-1)가 가능한 경우

위와 같이 $DP$ 테이블을 완성하고

$la=a.length(),lb=b.length()$라고 할 때

$la+lb$ 인덱스부터 $0$까지 내려가면서 역추적을 해주면 된다.

$ans[i]=DP(la,lb)$

만약 $c[i]==a[la]$ $and$ $DP(i-1,j)$가 가능한 경우라면

$DP(la-1,lb)$에서 온 것이기 때문에 $la$를 택한다.

만약 $c[i]==b[lb]$ $and$ $DP(i,j-1)$가 가능한 경우라면

$DP(la,lb-1)$에서 온 것이기 때문에 $lb$를 택한다.

이를 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string a,b,c;
    cin >> a >> b >> c;
    int la=a.length(),lb=b.length(),cnt=c.length();
    vector<vector<int>> dp(la+1,vector<int> (lb+1,0));
    vector<int> ans(cnt,0);
    dp[0][0]=1;
    for(int i=0;i<=la;i++) for(int j=0;j<=lb;j++){
        if(i && dp[i-1][j] && c[i+j-1]==a[i-1]) dp[i][j]=1;
        if(j && dp[i][j-1] && c[i+j-1]==b[j-1]) dp[i][j]=2;
    }
    for(int i=0;i<cnt;i++){
        ans[cnt-(i+1)]=dp[la][lb];
        if(dp[la][lb]==1) la--;
        else lb--;
    }
    for(int &t:ans) cout << t;
    return 0;
}