AB 문자열

면접 대비

시간 제한2초메모리 제한512 MB

요약

A가 B보다 앞서는 쌍의 개수가 K인 길이 N의 A/B 문자열 가운데 사전순으로 가장 앞선 것을 찾는다.

문제

정수 $N$ 과 $K$ 가 주어진다. 다음 두 조건을 모두 만족하는 문자열 $S$ 를 구하라.

$S$ 의 길이는 $N$ 이고, 문자 'A'와 'B'로만 이루어진다.
$0 \le i < j < N$ 이고 $S$ 의 $i$ 번 문자가 'A', $j$ 번 문자가 'B'인 쌍 $(i, j)$ 가 정확히 $K$ 개다. 문자의 위치는 0부터 센다.

조건을 만족하는 $S$ 가 여러 개면 사전순으로 가장 앞선 것을 구한다. 사전순 비교에서 'A'가 'B'보다 앞선다.

첫째 줄에 $N$ 과 $K$ 가 공백으로 구분되어 주어진다. ( $2 \le N \le 50$ , $0 \le K \le N(N-1)/2$ )

첫째 줄에 조건을 만족하는 문자열 $S$ 중 사전순으로 가장 앞선 것을 출력한다. 그런 $S$ 가 없으면 -1을 출력한다.