그리디 알고리즘 문제이다.
N 과 K를 가지고 A 의 개수와 B 의 개수를 알 수 있다.
예를 들어보자. N = 5, K = 5 인 경우를 보자 이때 A의 갯수를 0 부터 N 개까지 늘려가보자.
A의 갯수가 0인 경우 B의 갯수는 N인 5이다.
이때 만들 수 있는 쌍의 갯수는 0 개이므로 패쓰한다.
A의 갯수가 1인 경우 B의 갯수는 N-1 인 4이다.
이때 만들 수 있는 최대의 쌍의 갯수를 구해보자.
모든 A가 앞에 배치되고 모든 B가 A의 뒤에 배치되는 경우(ABBBB)가 가장 많은 쌍을 만들 수 있는 경우이다. A의 갯수가 1이고 B의 갯수가 4인 경우 만들 수 있는 최대의 쌍의 갯수는 1x4 = 4 개이다. 현재 예제에서 주어진 K는 5이다. 즉, A개 1개이고 B가 4개일 경우 K 개의 쌍을 만들 수 없다고 판단하고 A의 갯수를 늘린다.
그 이후 A의 개수가 2, B의 개수가 3인 경우 최대 쌍의 갯수는 6이고 K보다 크거나 같으므로 A의 개수와 B의 개수를 구했다고 판단한다.
그 다음으로 A의 위치를 찾아야 한다.
먼저 정답 문자열 배열을 모두 B로 채운다. (BBBBB)
그 다음 A의 갯수 - 1 (2-1 = 1개)을 한 개수 만큼 문자열의 앞에서부터 A로 채운다. (ABBBB)
그 다음 A를 문자열 제일 뒤에 대입해보자 (ABBBA)
이 경우 만들 수 있는 쌍의 개수는 3 개이다.
그 다음 제일 뒤에 있는 A를 한칸씩 앞으로 당겨보자.(ABBAB)
이 경우 만들 수 있는 쌍의 개수는 3개이다.
한칸 더 당겨보자.(ABABB)
이 경우 만들 수 있는 쌍의 개수는 K개인 5개로 만족하며 이를 출력하면 정답이다.
이렇게 뒤에서부터 한칸씩 당겨보면 만들 수 있는 쌍의 개수느가 한칸 당길때마다 + 1 된다.
public class bj12970 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] split = br.readLine().split(" ");
int N = Integer.parseInt(split[0]);
int K = Integer.parseInt(split[1]);
int aNum = 0;
int bNum = 0;
// A와 B의 개수를 구한다.
// A+B == N
for (int i = 0; i <= K; i++) {
aNum = i;
bNum = N - i;
// 이때 만들 수 있는 쌍의 최대 갯수는
// 모든 A가 앞에 있고 모든 B가 A 뒤에 위치할 때다
// 이때 최대 갯수가 K보다 작다면 K개를 만들 수 없으므로
// 다른 A 갯수, B 갯수를 찾는다
if (aNum * bNum >= K) {
break;
}
// 만들 수 없는 경우
if (i == K) {
System.out.println(-1);
System.exit(0);
}
}
String[] answer = new String[N];
Arrays.fill(answer, "B");
// K가 0일 경우 N을 모두 B로 채운 문자열을 출력하면 된다.
if (K == 0) {
for (String s : answer) {
System.out.print(s);
}
System.exit(0);
}
// A를 aNum - 1개 만큼 앞에서부터 채워준다.
for (int i = 0; i < aNum - 1; i++) {
answer[i] = "A";
}
// 이후 뒤에 A를 붙여보면
// 예) AAABBBA가 된다.
// 여기서 맨 뒤에 있는 A를 왼쪽으로 한칸씩 움직일 때마다
// 만들 수 있는 쌍의 갯수가 + 1씩 늘어나며
// 제일 왼쪽으로 가서 AAAABBB가 된다면
// 가장 많이 만들 수 있는 쌍의 갯수가 된다.
int currentTwins = (aNum - 1) * bNum;
int haveMoveA = K - currentTwins;
answer[N - 1 - haveMoveA] = "A";
for (String s : answer) {
System.out.print(s);
}
br.close();
}
}