12969 ABC

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

12969번: ABC

 

d[i][a][b][p] = 길이가 i이고, A의 개수가 a개, B의 개수가 b개, S[i]<S[j] 쌍이 p개 있는 문자열이 가능한가?

 

#include <cstdio>
 
bool d[31][31][31][400];
char ans[31];
int n,k;
 
bool go(int i,int a,int b,int p)
{
    if(i==n) return p==k;
    if(d[i][a][b][p]) return false;
    d[i][a][b][p]=true;
    ans[i]='A';
    if(go(i+1,a+1,b,p)) return true;
    ans[i]='B';
    if(go(i+1,a,b+1,p+a)) return true;
    ans[i]='C';
    if(go(i+1,a,b,p+a+b)) return true;
    return false;
}
 
int main()
{
    scanf("%d %d",&n,&k);
    printf("%s",go(0,0,0,0)?ans:"-1");
    return 0;
}