Python으로 각 접두사와 접미사에서 B의 개수가 A보다 많거나 같도록 문자열을 배열하는 경우의 수 구하기

n개의 'A'와 2n개의 'B'로 이루어진 문자열이 있다고 가정해 보겠습니다. 이때 문자열의 모든 접두사(prefix)와 모든 접미사(suffix)에서 'B'의 개수가 'A'의 개수보다 크거나 같도록 배열할 수 있는 경우의 수를 구하는 것이 이 글의 목표입니다.

예를 들어 n = 2라고 입력하면 'A'가 2개, 'B'가 4개 존재합니다. 조건을 만족하는 가능한 배치는 [BBAABB, BABABB, BBABAB, BABBAB]로 총 4가지이므로, 출력 결과는 4가 됩니다.

문제 해결 접근 방법

이 문제는 재귀(recursion)를 활용해 다음과 같은 단계로 해결할 수 있습니다.

• solve 메서드를 정의하고, 매개변수로 n을 전달받습니다.
• n이 1이면 1을 반환합니다.
• n이 2이면 4를 반환합니다.
• n이 홀수이면 solve((n-1)//2)의 제곱을 반환합니다.
• n이 짝수이면 solve(n//2)의 제곱을 반환합니다.

즉, 큰 입력값을 절반 크기의 하위 문제로 나누어 재귀적으로 풀고, 그 결과를 제곱하여 최종 답을 얻는 방식입니다. 기저 사례(base case)인 n = 1과 n = 2의 값을 미리 정의해 두면 재귀 호출이 안전하게 종료됩니다.

예제 코드

아래 파이썬 구현 예시를 통해 동작 과정을 더 쉽게 이해할 수 있습니다.

def solve(n):
   if n==1:
      return 1
   if n==2:
      return 4
   if n%2 != 0:
      return solve((n-1)//2)**2
   else:
      return solve(n//2)**2

n = 2
print(solve(n))

입력

2

출력

4

위 코드에서 n = 2가 입력되면 solve(2)가 바로 4를 반환하므로, 화면에는 4가 출력됩니다. 이처럼 재귀와 분할 정복 기법을 사용하면 복잡한 조합 문제도 간결한 코드로 해결할 수 있습니다.