BOJ 12970 - AB

입력

• 첫째 줄에 N과 K (2 ≤ N ≤ 50, 0 ≤ K ≤ N(N-1)/2)

출력

• (조건) 문자열 S의 길이가 N이고 'A', 'B'로 이루어져 있을 때, 문자열 S에는 0 ≤ i < j < N 이면서 s[i] == 'A' && s[j] == 'B'를 만족하는 (i, j) 쌍이 K개 있음
• 위의 조건을 만족하는 문자열 S를 출력

풀이 방법

• 먼저 가능한 S가 있는지를 체크한다.
  • (i, j) 쌍의 최대 개수인 N*N/4가 K보다 작은 경우, 가능한 S가 없으므로 -1을 출력한다. --- (경우의 수 1)
  • A의 개수를 a개, B의 개수를 (N-a)개로 설정했을 때 (i, j) 쌍의 최대 개수는 a*(N-a)개인데, 해당 식의 최댓값은 N*N/4이다.
• 가능한 S가 있을 때, (A의 개수)*(B의 개수) >= K를 만족하는 (A의 개수)*(B의 개수)가 최솟값일 때의 A, B 개수로 S를 만들 수 있다.
  • 위의 밑줄 친 조건을 만족할 때 (A의 개수)*(B의 개수) == K인 경우 "AAABBB"와 같이 "A"가 i번 반복되고, "B"가 (N-i)번 반복되는 형태이다. 즉, A와 B가 각각 연속해서 나타나는 형태이다.  --- (경우의 수 2)
  • 위의 밑줄 친 조건을 만족할 때 (A의 개수)*(B의 개수) > K인 경우, "AAABBABB"와 같이 "AAAABBBB"에서 가장 오른쪽 "A" 하나가 오른쪽으로 (i*(N-i)-K)번 움직인 형태이다.   --- (경우의 수 3)
  • 경우의 수 3의 경우, "BA"나 "ABA"와 같은 경우를 고려하여 Math.max()를 통해 예외 처리를 해준다.

---

(경우의 수 1)

예를 들어 N=5, K=8일 때 N*N/4는 6로, K보다 작으므로 가능한 S가 없다.

 

(경우의 수 2)

예를 들어 N=3, K=2라고 하자.

A의 개수	B의 개수	(A의 개수)*(B의 개수)
1	2	2

(A의 개수)*(B의 개수) >= 2를 만족하는 (A의 개수)*(B의 개수)의 최솟값은 2로, K와 일치한다.

따라서 A와 B의 개수는 각각 1개, 2개이고, 가능한 S는 "ABB"이다.

 

(경우의 수 3)

예를 들어 N=10, K=12라고 하자.

A의 개수	B의 개수	(A의 개수)*(B의 개수)
1	9	9
2	8	16
3	7	21
4	6	24
5	5	25

(A의 개수)*(B의 개수) >= 12를 만족하는 (A의 개수)*(B의 개수)의 최솟값은 16이고, 이때 A의 개수는 2개, B의 개수는 8개이다.

S는 A의 개수는 2개, B의 개수는 8개로 만들 수 있다.

AABBBBBBBB는 (i, j) 쌍의 개수가 16개이고,

ABABBBBBBB는 (i, j) 쌍의 개수가 15개이고,

ABABBBBBBB는 (i, j) 쌍의 개수가 14개이고,

ABBABBBBBB는 (i, j) 쌍의 개수가 13개이고,

ABBBABBBBB는 (i, j) 쌍의 개수가 12개이다.

즉, 해당 A와 B 개수를 이용하여 A와 B가 각각 연속하여 나타나는 형태의  AABBBBBBBB를 만든 뒤, 가장 오른쪽의 A 하나를 오른쪽으로 ( (A의 개수)*(B의 개수)와 K의 차 = i*(N-i)-K )만큼 이동시킨 문자열이 S이다.

해당 예시에서 (A의 개수)*(B의 개수)와 K의 차 = i*(N-i)-K = 4이므로 AABBBBBBBB의 오른쪽 A 하나를 오른쪽으로 4번 이동시킨 ABBBABBBBB가 가능한 S이다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_12970 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		
		int N = Integer.parseInt(input[0]);
		int K = Integer.parseInt(input[1]);
		
		// (i, j) 쌍의 최대 개수(N*N/4)가 K보다 작은 경우, 가능한 S가 없으므로 -1 출력
		if(N*N/4 < K) {
			System.out.println(-1);
		}
		// 가능한 S가 있는 경우
		else {
			String ans = "";	// 가능한 S 저장할 변수 (출력값)
			
			// A의 개수를 i개, B의 개수를 (N-i)개라고 설정
			// (A의 개수)*(B의 개수)>=K를 만족하는 (A의 개수)*(B의 개수)가 최솟값일 때의 A, B 개수로 S를 만들 수 있음
			// 경우의 수 1. (A의 개수)*(B의 개수)==K를 만족하는 A, B 개수가 있다면, "AAABBB"와 같이 "A"가 i번 반복되고, "B"가 (N-i)번 반복되는 형태임
			// 경우의 수 2. (A의 개수)*(B의 개수)==K를 만족하는 A, B 개수가 없고 (A의 개수)*(B의 개수)>K인 경우, "AAABBABB"와 같이 "AAAABBBB"에서 가장 오른쪽 "A"가 오른쪽으로 (i*(N-i)-K)번 움직인 형태임
			// (예외) 경우의 수 2에서 "BA"나 "ABA"와 같은 경우를 고려하여 Math.max()를 통해 예외 처리
			for(int i=1;i<=N/2;i++) {
				if(i*(N-i) < K) {
					continue;
				} else if(i*(N-i)== K) {
					ans = "A".repeat(i) + "B".repeat(N-i);
					break;
				} else {
					// "A"는 i개, "B"는 (N-i)개
					ans = "A".repeat(Math.max(0, i-1)) + "B".repeat(i*(N-i)-K) + "A" + "B".repeat(Math.max(0,N-i+K-i*(N-i)));
					break;
				}
			}
			
			System.out.println(ans);
		}
	}
}