[그리디 알고리즘] AB

예제 입력 1

3 2

예제 출력 1

ABB

예제 입력 2

2 0

예제 출력 2

BA

예제 입력 3

5 8

예제 출력 3

-1

예제 입력 4

10 12

예제 출력 4

BAABBABAAB

 

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

12970번: AB

- A가 a개 있고, B가 b개 있으면(a+b == N) 0 <= i < j < N이면서 s[i] == 'A', s[j] == 'B'를 만족하는 쌍을 0 ~ a*b개 만들 수 있다. 

- BBBBBB가 있을 때, A를 맨 앞에 두면 6쌍, A를 제일 끝에 두면 0쌍 이런식이며 A를 계속 추가하여 늘릴 수 있다.

- 먼저 A+B == N을 만족하도록 A와 B의 개수를 각각 정해보면서, K <= a*b 이면 K개 만들 수 있으므로 만족하는 경우를 문제의 조건에 따라 아무거나 출력하면 된다.

#include <stdio.h>

const int MAX_COUNT = 51;

int N, K;
int arr[MAX_COUNT];

inline int MIN(int a, int b)
{
	return a < b ? a : b;
}

int main(void)
{
	scanf("%d %d", &N, &K);

	for (int a = 0; a <= N; a++)
	{
		int b = N - a;

		if (a * b < K) continue;

		for (int i = 0; i < a; i++)
		{
			int x = MIN(b, K);
			arr[x] += 1;
			K -= x;
		}

		for (int i = b; i >= 0; i--)
		{
			for (int j = 0; j < arr[i]; j++)
			{
				printf("A");
			}

			if (i > 0) printf("B");
		}

		printf("\n");
		return 0;
	}

	printf("-1\n");
	return 0;
}