합이 고정된 두 수의 곱 최대화: A를 앞에, C를 뒤에 반씩 배치하기

그래서 답은 N / 2개의 A 뒤에 (N + 1) / 2개의 C를 붙인 문자열이고, 쌍의 수는 그 두 값의 곱이다.

배치: 왜 A를 전부 앞에 두는가

A가 a개, C가 c개 있다고 하자. 순서쌍은 위치 i < j에 대해 S[i] = 'A', S[j] = 'C'인 경우다. A 하나와 C 하나를 고르는 방법은 모두 a × c가지이므로, 어떤 배치를 하든 쌍의 수는 a × c를 넘을 수 없다.

길이 N인 문자열을 A와 C로만 채운다고 하자. 앞에 있는 A 하나와 뒤에 있는 C 하나를 고르면 순서쌍 하나가 생긴다. 이 쌍의 개수를 최대로 만드는 문자열을 구성할 때 핵심 관찰은 두 가지다. 첫째, A를 모두 C보다 앞에 두면 가능한 모든 조합이 쌍이 된다. 둘째, 그 조합의 수는 A의 개수와 C의 개수의 곱이며, 합이 N으로 고정된 두 정수의 곱은 둘을 최대한 비슷하게 나눌 때 가장 크다.

이 상한은 A를 모두 앞에 몰아넣으면 정확히 달성된다. AA…ACC…C 꼴에서는 어떤 A를 고르든 모든 C가 그 뒤에 있으므로, 고를 수 있는 모든 (A, C) 조합이 유효한 쌍이 된다. 반대로 C가 어떤 A보다 앞에 오면 그 C와 그 A의 조합은 쌍이 되지 못하고 손해가 생긴다.

결국 배치 문제는 사라지고, 남는 것은 a + c = N일 때 a × c를 최대로 만드는 개수 분배 문제다.

개수 분배: 합이 고정된 곱의 최댓값

a개를 A로 정하면 C는 N − a개이고, 곱은 f(a) = a(N − a)다. 이 식은 위로 볼록한 이차함수이며 꼭짓점은 a = N/2이다. 꼭짓점에서 멀어질수록 값이 줄어든다.

정수만 쓸 수 있으므로 N이 짝수면 a = c = N/2, 홀수면 한쪽이 ⌊N/2⌋, 다른 쪽이 ⌈N/2⌉일 때 최대다. 다르게 보면 a × c = ((a + c)² − (a − c)²) / 4이므로, 합이 고정된 상태에서는 차이 |a − c|가 작을수록 곱이 커진다. 차이를 0이나 1로 만드는 분배가 최선이다.

N = 5를 예로 들면 가능한 분배와 곱은 다음과 같다.

A 개수	C 개수	곱
1	4	4
2	3	6
3	2	6
4	1	4

2와 3으로 나눈 AACCC에서 6개의 쌍이 나오고, 이것이 최댓값이다. 홀수일 때 남는 한 글자를 어느 쪽에 줘도 곱은 같다.

코드와의 연결

위의 두 관찰이 코드에서는 세 줄로 옮겨졌다. N / 2가 ⌊N/2⌋, (N + 1) / 2가 ⌈N/2⌉ 역할을 한다.

ll M = ((ll)N / 2) * ((N + 1) / 2);
string S;
for (int i = 0; i < N / 2; i++) S.push_back('A');
for (int i = 0; i < (N + 1) / 2; i++) S.push_back('C');

M은 A 개수와 C 개수의 곱, 즉 최대 쌍 수다. S는 A를 먼저 N / 2개 넣고 C를 (N + 1) / 2개 이어 붙여 만든다. 두 개수의 합은 정확히 N이다. 홀수 N에서는 C가 하나 더 많은데, 앞의 표에서 보았듯 결과는 같다.

곱은 상수 시간에 계산하고, 문자열은 글자를 하나씩 붙이므로 시간과 공간 모두 O(N)이다.

자료형에 관한 수정과 남은 문제

중간에 M의 자료형을 int로 바꿨다가 다시 ll로 되돌렸다. (ll)N / 2로 첫 피연산자를 넓혀 곱셈 자체는 long long으로 수행되더라도, 결과를 int에 담으면 int 범위를 넘는 값은 제대로 보존되지 않는다. 곱은 대략 N² / 4이므로 N이 수만 단위만 되어도 int를 넘을 수 있다. 최종 코드처럼 ll에 저장하는 편이 안전하다. 그 사이에 solve 호출 반복문을 잠시 solve 내부로 옮겨 종료 조건 없는 재귀가 되었던 적도 있지만, 바로 main으로 되돌려 원래 구조를 복구했다.

다만 최종 코드에도 넓혀지지 않은 연산이 하나 남아 있다. (N + 1)은 곱셈 식과 두 번째 반복문 조건 두 곳 모두 int 덧셈이다. 입력으로 INT_MAX가 허용된다면 이 덧셈에서 오버플로가 일어난다. 그런 범위까지 대비하려면 두 곳 모두 (1LL * N + 1) / 2처럼 덧셈 전에 자료형을 넓혀야 한다. 물론 그 정도 길이라면 문자열 자체를 만드는 것부터 현실적이지 않으므로, 실제로 문제가 되는지는 입력 범위에 달려 있다.

정리하면 이 풀이는 "배치로 상한을 달성하고, 상한 자체를 최대화한다"는 두 단계 구성이다. 쌍의 수가 a × c를 넘을 수 없다는 상한과 그 상한을 정확히 채우는 배치를 찾으면, 문자열 문제가 합이 고정된 두 수의 곱을 최대화하는 단순한 문제로 바뀐다.