[백준] 12970 AB - JAVA

문제

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

풀이과정

먼저 K로 알 수 있는 사실은 정답 문자열에서 A의 개수가 몇개인지이다.
N=12이고 K=27일때 정답에서의 A개수를 어떻게 알 수 있을까?

A가 1개라면 B는 11개가 되야하고 AB순서쌍의 최대개수는 A가 가장 왼쪽에 위치할때 구할 수 있다.
즉 AB쌍의 개수는 11개가된다.

A가 2개라면 B는 10개가 되야하고 AB순서쌍의 최대개수는 AABBBBBBBBBB 일때이다.
이때 AB쌍의 개수는 20개가 된다.

여기서 알 수 있는 사실은 N과 K가 주어졌을때 A의개수*B의 개수가 K보다 크거나 같으면 해당 개수로 문자열을 만들 수 있다는 사실이다. 이를 통해 A의 개수를 구하는 함수를 만들어 주었다.

public static int checkALength() {
    int ALength = 1;
    int BLength = N - 1;
    while(ALength*BLength < K) {
      if(BLength < 0) return -1;
      ALength++;
      BLength--;
    }
    return ALength;
}

A의 개수를 알았으니 B의 개수도 저절로 알게된다 (N-A의 개수)

이제 어떻게하면 알아낸 A와B의 개수로 정답을 알 수 있을까??
N=12이고 K=26이라고 해보자 checkALength 함수를 통해 A가 3 B가 9개가 있어야 한다는걸 알 수 있다.
이제 문자열을 N의 개수만큼 다 B로 채워준다.
BBBBBBBBBBBB
여기서 A의 개수 - 1 만큼 제일 왼쪽부터 A로 채워준다.
AABBBBBBBBBB
여기서 마지막 부분을 A로 만들어준다.
AABBBBBBBBBA
여기서 중요한 부분은 마지막 문자의 A를 왼쪽으로 이동할때마다 AB순서쌍의 개수가 1씩증가한다는 사실이다.

AABBBBBBBBBA -> AB쌍: 18 ((A개수 - 1)B의 개수)
AABBBBBBBBAB -> AB쌍: 19 ((A개수 - 1)B의 개수 + 1)
AABBBBBBBABB -> AB쌍: 20 ((A개수 - 1)B의 개수 + 2)
...
AABABBBBBBBB -> AB쌍: 27 ((A개수 - 1)B의 개수 + 8) 정답!

즉 (A개수 - 1)*B의 개수를 c라고 할때 K-c만큼 마지막 A를 왼쪽으로 이동해야 원하는 답을 얻을 수 있다.
이말은 해당 문자열에서 N-1-(K-c)의 인덱스를 A로 해주면 된다는 말이다.

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
  static int N;
  static int K;
  static int ALength = 0;
  static String s = "";
  static String[] result;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    K = Integer.parseInt(st.nextToken());
    ALength = checkALength();
    int BLength = N - ALength;
    result = new String[N];
    if(ALength != -1 && K != 0) {
      for(int i=0; i<N; i++) {
        result[i] = "B";
      }
      for(int i=0; i<ALength-1; i++) {
        result[i] = "A";
      }
      int c = (ALength - 1) * BLength;
      int r = K - c;
      result[(N-1)-r] = "A";
    }
    else if (K == 0) {
      for(int i=0; i<N; i++) {
        result[i] = "B";
      }
    }
    System.out.println(ALength == -1 ? -1 : String.join("", result));
  }
  public static int checkALength() {
    int ALength = 1;
    int BLength = N - 1;
    while(ALength*BLength < K) {
      if(BLength < 0) return -1;
      ALength++;
      BLength--;
    }
    return ALength;
  }
}