[BOJ/백준][Gold4] 12970 : AB (C++)

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

12970번: AB

 

[난이도] Gold4
[유형] DP

[풀이]
dp[n][a][k] : 앞에서부터 n개의 문자를 배치했고, A의 개수가 a개이며, AB쌍의 수의 k개일 때, 정답 문자열을 만들 수 있는지 여부 (1:ok,0:no,-1:아직 체크안됨)

A를 추가하는 경우 => sol(n+1,a+1,k) 이 1이면 문자열을 만들 수 있으므로 정답 문자열에 'A'를 추가,
B를 추가하는 경우 => sol(n+1,a,k+a) 이 1이면 문자열을 만들 수 있으므로 정답 문자열에 'B'를 추가하는

 

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int N,K,dp[50][50][13000];
string r;
int sol(int n,int a,int k){
    if(n==N) return k==K;
    int& ret = dp[n][a][k];
    if(ret!=-1) return ret;

    int b = n-a;
    if(sol(n+1,a+1,k)){
        r = 'A' + r;
        return ret=1;
    }

    if(sol(n+1,a,k+a)){
        r = 'B' + r;
        return ret=1;
    }
    return ret=0;
}
int main(){
    cin >> N >> K;
    memset(dp,-1,sizeof(dp));
    sol(0,0,0);
    if(r=="") cout << -1;
    else cout << r;
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/12970.cpp