달과 우산 timer 10s memory 1024MB

코디-자말(Cody-Jamal)은 최신 추상미술 작품을 만들고 있다. 이 작품은 점점 이지러지는 달(waning moon)과 접힌 우산(closed umbrella)들이 한 줄로 배열된 벽화이다. 하지만 탐욕스러운 저작권 트롤들이, 이지러지는 달이 대문자 C처럼 보이고 접힌 우산이 J처럼 보인다며, 문자열 CJ와 JC에 대한 저작권을 주장하고 있다. 그래서 벽화에 CJ가 나타날 때마다 코디-자말은 \mathbf{X}를 지불해야 하고, JC가 나타날 때마다 \mathbf{Y}를 지불해야 한다.

코디-자말은 이미 그려진 부분을 바꿔 예술을 훼손하고 싶지 않다. 하지만 아직 비어 있는 칸들은 전략적으로 채워 저작권 비용을 최소화할 수 있다고 생각했다.

예를 들어 벽화의 현재 상태가 CJ?CC?라고 하자. 여기서 C는 이지러지는 달, J는 접힌 우산, ?는 아직 그려지지 않았으며 달 또는 우산 중 하나로 채워야 하는 칸을 의미한다. 코디-자말은 벽화를 CJCCCC, CJCCCJ, CJJCCC, CJJCCJ 중 하나로 완성할 수 있다. 첫 번째와 세 번째 선택지는 저작권 비용이 \mathbf{X} + \mathbf{Y}이고, 두 번째와 네 번째 선택지는 2 \cdot \mathbf{X} + \mathbf{Y}가 된다.

비용 \mathbf{X}, \mathbf{Y}와 벽화의 현재 상태를 나타내는 문자열이 주어질 때, 완성된 벽화의 저작권 비용이 최소가 되도록 빈 칸을 채운다면 코디-자말이 지불해야 하는 저작권 비용은 얼마인가?