5293. 이진 문자열 복원

"00" "01" "10" "11" 을 이진 문자열의 재료이고 각각 A,B,C,D개 있을 때 이것을 조합하여 이진 문자열이 만들어진다면

해당 문자열(중복정답 가능)을 출력하고 불가능하다면 impossible을 출력하는 문제다.

DP로 접근을 해보자.

길이가 n인 이진문자열이 있을 때 이것을 가지고 n+1길이의 이진문자열을 만들기 위해서 필요한 것은

1. 사용된 이진 문자열 재료의 개수 a,b,c,d

2. 2진수의 끝자리

이다. 0<=A,B,C,D<=20 이므로 dp[21][21][21][21][2] 테이블을 만들 수 있고 이걸 채우면 된다.

#include <iostream>
#include <string.h>
#include <string>
using namespace std;
 
string dp[21][21][21][21][2];
bool check[21][21][21][21][2];
 
void run(int aa, int bb, int cc, int dd, int bit) {
    string &ret = dp[aa][bb][cc][dd][bit];
    if (check[aa][bb][cc][dd][bit]) return;
    check[aa][bb][cc][dd][bit] = 1;
    if (aa && !bit) {
        run(aa - 1, bb, cc, dd, 0);
        if (dp[aa - 1][bb][cc][dd][0].length()) {
            ret = dp[aa - 1][bb][cc][dd][0] + "0";
            return;
        }
    }
    if (bb && bit) {
        run(aa, bb - 1, cc, dd, 0);
        if (dp[aa][bb - 1][cc][dd][0].length()) {
            ret = dp[aa][bb - 1][cc][dd][0] + "1";
            return;
        }
    }
    if (cc && !bit) {
        run(aa, bb, cc - 1, dd, 1);
        if (dp[aa][bb][cc - 1][dd][1].length()) {
            ret = dp[aa][bb][cc - 1][dd][1] + "0";
            return;
        }
    }
    if (dd && bit) {
        run(aa, bb, cc, dd - 1, 1);
        if (dp[aa][bb][cc][dd - 1][1].length()) {
            ret = dp[aa][bb][cc][dd - 1][1] + "1";
            return;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc, c2 = 0;
    cin >> tc;
    dp[1][0][0][0][0] = "00";
    dp[0][1][0][0][1] = "01";
    dp[0][0][1][0][0] = "10";
    dp[0][0][0][1][1] = "11";
 
    for (int t = 1; t <= tc; ++t) {
        int aa, bb, cc, dd;
        cin >> aa >> bb >> cc >> dd;
        cout << "#" << t << " ";
        run(aa, bb, cc, dd, 0);
        run(aa, bb, cc, dd, 1);
        if (dp[aa][bb][cc][dd][0].length())
            cout << dp[aa][bb][cc][dd][0];
        else if (dp[aa][bb][cc][dd][1].length())
            cout << dp[aa][bb][cc][dd][1];
        else
            cout << "impossible";
        cout << '\n';
    }
    return 0;
}