wbluke
commented
5 years ago [My Point]
- 무식하게 풀기에는 Case의 수가 너무 크다...
[Idea Point]
- 놀랍게도 두 큰 수의 곱셈을 행하는 알고리즘에서 이 문제의 해결책을 발견할 수 있다.
- 각 자릿수들의 곱들을 모두 계산하고, 각 세로줄의 합 Ci를 구한 뒤 올림처리를 하는 곱셈 알고리즘에서,
Ci = A0*Bi + A1*B(i-1) + A2*B(i-2)라는 점화식이 나온다. 문제의 상황에 맞게 순서를 뒤집으면,Ci = A2*Bi + A1*B(i-1) + A0*B(i-2)가 된다. - 남성은 1, 여성은 0으로 표현했을 때, 올림수를 무시하고 각 자리의 모든 Ci가 0이라면, 이는 동시에 포옹을 하고 있다는 뜻이 된다. 1*1만 1이고 나머지는 0이기 때문이다.
- 큰 수의 곱셈이므로 여기서 카라츠바 알고리즘을 구현하면 더 시간복잡도를 줄일 수 있다.
https://algospot.com/judge/problem/read/FANMEETING
APSS_p201