[BOJ 12970] AB (Java)

BOJ 12970 AB

문제풀이

이 블로그를 보고 풀었다(공부했다).

먼저 재귀를 활용한 완전탐색을 생각했지만 최악의 경우 문자열을 만드는 것에만 2^50 이다. 따라서 문자열의 배치에 따른 규칙을 찾아 그에 따라 구현해야한다.

• 두 가지를 고려해야하는 경우 한 가지를 고정시켜놓고 나머지 한 가지를 조절하는 아이디어가 유용하다. 이 문제에서는 A, B를 배치해야하지만 B를 배치해놓고 그 사이에 A를 어떻게 배치할지를 생각하면 되겠다.

• 또한 배치를 하였을 때 순서쌍의 최댓값은 A의 개수 * B의 개수 라는 것을 알 수 있다. 따라서 A, B의 개수를 정했을 때 A의 개수 * B의 개수가 K보다 작을 경우에는 다음 과정을 수행할 필요가 없다.

• A를 배치하였을 때 A의 오른쪽에 B의 개수만큼 순서쌍이 만들어진다. 따라서 필요한 만큼의 순서쌍이 만들어지는 위치에 A를 배치하면 된다. 문자열의 길이를 충족하기 전에 K를 충족하였다면 마지막에 A를 부족한 길이만큼 붙힌다.

구현코드

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

public class Main {
	
	static int N, K;
	
	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());
		
		for(int a = 0 ; a <= N ; ++a) {
			int b = N - a;
			
			// AB 쌍의 최대 갯수는 a * b 이므로 최대갯수가 K 미만일 경우는 넘어간다.
			if(a * b < K) continue;
			
			// B를 먼저 놔두고 A를 배치한다. 따라서 A가 위치할 수 있는 곳은 b + 1 곳 이다.
			// A[i] 는 i번째 들어갈 A의 갯수 
			// 좌우반전을 하여 수행한다. 
			int[] A = new int[b + 1];
			for(int i = 0 ; i < a ; ++i) {
				// A의 오른쪽에 B의 갯수만큼 순서쌍이 생긴다. 
				// 한 번에 최대 만들 수 있는 순서쌍은 b개
				// 따라서 K와 b중 작은 값의 위치에 A를 위치시킨다면 필요한 만큼 순서쌍을 만들 수 있다. 
				int idx = K > b ? b : K;
				
				// 지정한 위치에 A를 배치한다. 
				A[idx]++;
				// 생성된 순서쌍을 K에서 뺀다. 
				K -= idx;
			}
			
			for(int i = b ; i >= 0 ; --i) {
				for(int j = 0 ; j < A[i] ; ++j) {
					System.out.print("A");
				}
				// 마지막 B는 순서쌍을 더 만들게 되므로 추가하지 않는다.
				if(i > 0) System.out.print("B");
			}
			return;
		}
		
		// 만들지 못하는 경우 
		System.out.println(-1);
	}
}