BOJ 13423 Three Dots

나에겐 매우 어려운 문제였다. 결국 나는 생각하지 못했고, 풀이를 보고 풀었다.

나는 그냥 O(N^3)짜리 코드를 짰는데, for문 형태만 N^3이고, 사실은 N^2일 것이라고 단단히 착각하고 있었다... 계속해서 TLE를 받고 풀이를 보기 전까지...

풀이를 다시 보고 풀고 생각해보니 시간 복잡도 계산이 그리 간단치 않아서
직접 계산해봤다.

대충 계산을 해보면,
(n-1)*(n-2) + (n-2)*(n-3) + (n-3)*(n-4) + .... + 2*1 이렇게 될 것인데,
이것은 SUM(k=1 ~ n, (n-k)*(n-(k+1)) ) 이 될 것이다. 시그마를 써서 표현하면 더 알아보기 쉬울텐데, 일단은 이렇게 쓰겠다.
식으로 풀어써서 계산을 해보면 (맞는진 모르겠지만..) (n^3 - 3*n^2 + 2*n)/3 이 나온다.
즉 O(N^3)으로 볼 수 있다.

이거 계산하면서 느낀 것이... 일단 매우 오래 걸렸고, 수학 공부 좀 할껄... 아니 이제와서 후회해봤자 소용없으니, 앞으로 수학 공부좀 하자라는 생각이 들었다. 공부하자. 알고리즘 잘하려면 수학적 센스도 필요하고 수학적 개념이 많이 필요한 것 같다.

자, 이제 다시 문제로 돌아와서 저렇게 O(N^3)으로 구현하면 시간초과가 난다.
그래서 일단 앞의 두 개의 수 a, b만 먼저 찾고(일단 중복 방지를 위해 sorting이 되어 있다.) 세번째 수c는 b+(b-a)가 있는지를 해싱이나, 이분 탐색으로 탐색해서 존재하면 count해주는 식으로 하면 O(N^2 logN)이 된다.

난 map을 써서 배열의 수를 다 저장해두고, 이분탐색 대신 map.count를 이용해서 그 수가 존재하는지 확인하는 방법을 사용했는데, 또 시간초과가 났다.
map도 binary tree로 구현되어 있어서 map.count하면 binary search와 비슷할 것 같은데...음... 일단 이 부분은 나중에 찾아보기로 하고 map.find를 써봤는데, 역시 시간초과이다.
물론 내가 사용법을 잘 몰라서 잘못 썼을 가능성도 있다.

일단은 좀 힘과 의욕이 많이 떨어진 상태라 더 안 찾아보고 이분 탐색으로 구현했더니 AC를 받았다.
그리고 고수분들의 코드를 확인하고 O(N^2)의 방법을 알 수 있었다.

O(N^2)의 방법은 다음과 같다.
일단 모든 수를 가운데 수b를 먼저 정한다. 그리고 배열의 양 끝에서 각각 a, c의 후보가 되는 수들을 차례 차례 본다.
그러면서 b-a > c-b 이면 aIdx++, b-a==c-b인 경우 count, b-a < c-b 이면 cIdx--.
이렇게 구하면 가운데 수 b에 대해서 N번씩 보면 되므로 O(N^2)이다. 멋지다.

오늘은 정말 내가 엄청 못한다는 것과 여태 좀 한다는 착각에 단단히 빠져있었다는 것을 깨달았다.

참고 : 국민대학교 교내 대회 풀이 슬라이드