[백준 3257] 발코딩

문제

www.acmicpc.net/problem/3257

 

알고리즘

다이나믹 프로그래밍

 

풀이

문자열 A,B와 그들을 섞은 C가 주어졌을 때 C의 문자들이 A에 속한 문자인지 B에 속한 문자인지 찾는 문제입니다. 단 C에서 문자열 A와 B는 원래 문자열의 순서를 유지합니다.

 

C에서 A와 B가 원래 순서를 유지하므로 C[1:]로 문제가 작아졌을 때 주어진 A,B 또한 A[1:],B 또는 A,B[1:]로 좁혀나갈 수 있습니다. 부분구조가 성립하므로 다이나믹 프로그래밍을 사용하도록 합시다.

 

$cache[i][j]$ = A문자열을 $i$번째까지 해결하고 B문자열을  $j$번째까지 해결했을 때, 해야하는 선택

 

즉 $cache[i][j]$값에 1이 들어있다면 $cache[i-1][j]$에서 A를 선택한 것이고, 반대로 2가 들어있다면 $cache[i][j-1]$에서 B를 선택한 것입니다. 나머지 실제 해를 찾는 것은 재귀함수를 통해 해결가능합니다. 시간복잡도는 $O(N^2)$ 입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FASTIO cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

char A[151], B[151], C[301];
int cache[151][151];
int al, bl;

void recur(int a, int b) {
    if (a == 0 && b == 0) return;
    if (cache[a][b]==1) recur(a - 1, b);
    else if (cache[a][b]==2) recur(a, b - 1);
    cout << cache[a][b];
}

int main() {
    FASTIO;
    cin >> A >> B >> C;
    al = strlen(A);
    bl = strlen(B);

    cache[0][0] = 1;
    for (int i = 0;i <= al;++i) {
        for (int j = 0;j <= bl;++j) {
            if (cache[i][j]) {
                if (C[i + j] == A[i]) cache[i + 1][j] = 1;
                if (C[i + j] == B[j]) cache[i][j + 1] = 2;
            }
        }
    }
    recur(al, bl);


    return 0;
}