[BOJ 12970 // C++] AB

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 12970번 문제인 AB이다.
문제는 아래 링크를 확인하자.

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

12970번: AB

글쓴이는 아래와 같은 전략을 이용하였다.

1) A를 N/2개, B를 N-N/2개 이용할 것이다. AB 개수의 최댓값은 (A의 개수)*(B의 개수)가 된다.

1-1) K가 AB 개수의 최댓값을 넘어간다면 -1을 출력해주자.

 

2) 정수 AA를 K/B, BB를 K%B라 하자.

문자열의 시작에 AA개의 'A'를, 문자열의 끝을 'A' 하나와 'B' BB개를 쓴 뒤 남은 'A'를 채워넣고 시작과 끝 사이에는 남은 'B'를 채워넣으면 K개의 AB가 포함된 문자열을 얻을 수 있다. 시작부분의 A가 포함된 K/B쌍의 AB와 뒤에 따로 있는 A가 포함된 K%B쌍의 AB의 개수를 합하면 K쌍의 AB를 얻을 수 있기 때문이다.

 

이와 같이 구현할 때, K가 가능한 최댓값이 주어진 경우를 보더케이스로 생각해야함에 유의하자. (잔여 A가 남지 않기 때문이다)

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, K; cin >> N >> K;
	int A = N / 2; int B = N - A;

	if (K > A * B) cout << -1;
	else if (K == A * B) {
		while (A--) cout << 'A';
		while (B--) cout << 'B';
	}
	else {
		int AA = K / B, BB = K % B;
		int aa = A - AA - 1, bb = B - BB;
		while (AA--) cout << 'A';
		while (bb--) cout << 'B';
		cout << 'A';
		while (BB--) cout << 'B';
		while (aa--) cout << 'A';
	}
}