[C++] 알고스팟/분할정복 - 팬미팅

문제 링크

https://algospot.com/judge/problem/read/FANMEETING

algospot.com :: FANMEETING

 

아이돌 그룹과 팬들이 다음과 같이 있는 상황에서

팬들이 왼쪽으로 한칸씩 움직이며 아이돌 그룹을 한명씩 만나게 됩니다.

 

남자끼리 만나는 경우 포옹을 하지 못하는데 움직이는 상황마다 포옹을 못한 팬들을 세어보면

첫번째부터 1, 2, 3, 2, 1명이 포옹을 하지 못하고 마지막의 경우에만 모든 팬들이 포옹을 할 수 있습니다.

 

이러한 숫자는 남자를 1, 여자를 0으로 놓고 팬들을 역순으로 바꾼다음 곱하면 이러한 값을 구할 수 있습니다.

 

하지만 멤버와 팬들의 수가 최대 20만 이므로 이렇게 큰 수를 곱셈을 하기 위해서는 카라츠바 알고리즘을 사용해서 구할 수 있습니다.

 

카라츠바 알고리즘은 분할정복 방식으로 큰 수의 곱셈을 하는 알고리즘인데 여기서 설명하기에는 너무 길어지므로 설명을 코드에 주석으로 남겨놓겠습니다.

 

카라츠바 알고리즘을 사용하면 아래와 같이 123 * 456 을 각 숫자의 자리수마다 배열에 담아 두 배열의 수를 곱한 값을 역순으로 구해줍니다. 123 * 456 = 56088

 

따라서 멤버와 팬들을 카라츠바 알고리즘을 사용하면 아래와 같이 구할 수 있습니다.

마지막으로 배열에서 0을 모두 세어주면 되는데 첫번째부터 다섯번째 값 까지는 모든 멤버가 팬들을 만나지 못한 경우이기 때문에 모든 멤버가 팬을 만난 시점인 멤버수-1 부터시작해서 팬들수-1 까지만 탐색하면 됩니다.

 

 

구현 코드