문제 : 팬미팅 (난이도 上)
분석
문제를 푸는 가장 간단한 방법은 문제에 나와 있는 과정 하나하나 시뮬레이션을 하는 것이다.
그러나 멤버와 팬의 수가 각각 20만에 달하는 수이기에 이렇게 풀기엔 무리이다.
하지만 앞서 배운 카르츠바 알고리즘을 알고 있으면 문제가 쉽게 해결된다.
2020/11/14 - [알고리즘 문제 해결 전략] - 분할 정복 - 카라츠바 알고리즘
카라츠바의 곱셈 순서가 문제에 나와 있는 그림 순으로 진행 된다는 것을 알 수 있다.
구현
int hugs(const string& members, const string& fans)
{
int N = members.size(), M = fans.size();
vector<int> A(N), B(M);
for (int i = 0; i < N; i++)
{
A[i] = (members[i] == 'M');
}
for (int i = 0; i < M; i++)
{
B[M - i - 1] = (fans[i] == 'M');
}
vector<int> C = karatsuba(A, B);
int hugAll = 0;
//모든 맴버가 안기를 하는 경우이므로 i = N - 1 ~
for (int i = N - 1; i < M; i++)
{
if (C[i] == 0) hugAll++;
}
return hugAll;
}
시간 복잡도
카라츠바 알고리즘의 시간 복잡도인 O(n^lg3) 이 나온다.
'알고리즘 > 알고리즘 문제 해결 전략' 카테고리의 다른 글
동적 계획법 - 1. 외발 뛰기 (0) | 2020.12.07 |
---|---|
동적 계획법 & 메모이제이션 (0) | 2020.11.26 |
분할 정복 - 2. 울타리 잘라내기 (0) | 2020.11.22 |
분할 정복 - 1. 쿼드 트리 뒤집기 (0) | 2020.11.16 |
분할 정복 - 카라츠바 알고리즘 (1) | 2020.11.14 |