[문제 출처 : Codechef] $N$개의 나무 막대기를 가지고 있다고 해 봅시다. 그리고 $N$개의 나무 막대기의 길이는 각각 $L_i$, $1\le i\le N$으로 주어져 있습니다. 만약 여러분의 친구가 와서 “내가 임의로 세 개의 막대기를 뽑아서 삼각형을 만들 수 있으면 내가 이긴거고, 못 만들면 네가 이긴거야 :)”라고 말했을 때, 여러분은 여러분이 이길 확률을 구하고 싶겠죠? $N$개의 막대기 중 임의로 3개를 뽑았을 때 그것이 삼각형을 이루지 못하는 경우는 몇 가지일까요?
먼저 삼각형을 이루지 못하는 경우는 어떤 경우일까요? 마치 중학교 수학시간으로 돌아간 기분인데요,(요즘 애들은 초등학교부터 배울까요?ㅎㅎ) 어떤 한 변의 길이가 다른 두 변의 길이의 합보다 크면 삼각형을 만들 수 없게 됩니다! 즉, \[a>b+c\] 를 만족하게 되면 삼각형을 만들 수 없게 됩니다.
그럼 이제 int N으로 전체 막대기의 수가 주어지고, int *L로써 각 막대기의 길이가 주어졌을 때, triplet의 개수를 어떻게 하면 구할 수 있을까요?
가장 직관적으로 생각할 수 있는 방법은 $N$개 중에 3개를 뽑아보고 그 중의 2가지를 뽑아서 합을 내어 비교해 보는 방법입니다. 이럴 경우 \[O\left({N\choose 3}\times{3\choose 2}\right)\approx O(N^3)\] 라는 별로 보고싶지 않은 숫자가 지수로 등장하게 되네요.. ㅎㅎ 따라서 우리는 좀 더 효율적인 알고리즘을 생각해 봅시다.
그것은 바로 이전 여러 예제들에서 언급했던 Sorting을 이용한 trick입니다! 만약에 우리가 역순으로 정렬된 $L$을 가지고 있다고 가정해 봅시다. 그리고 첫번째부터 $N-2$번째까지 반복하여 하나를 집어들고, 그 뒤의 막대기들 중 right를 가장 마지막인 $N$번째 막대기로, left를 아까 집어든 막대기보다 바로 짧은 막대기로 설정합니다. 어떻게 보면 이것이 합이 S인 두 수 찾기의 트릭과 비슷한데요, left와 right의 막대기의 합과 첫번째로 든 막대기의 길이를 비교해서(당연히 내림차순 정렬된 상태니까 기준으로 든 막대기가 제일 길겠죠?)
예를 들면, [100, 5, 4, 3] 이렇게 주어졌다고 했을 경우, 기준을 100으로 잡았을 때, $left+right=5+3=8<100$이므로 자동적으로 $left=4, right=3$의 조합도 삼각형이 될 수 없게 됩니다!
따라서 이 경우 right-left만큼 만들 수 없는 삼각형이 나오게 됩니다.
그럼 이제 이 합보다 바로 큰 합은 어떻게 만들까요? 합이 S인 두 수 찾기에서 설명한 것처럼 right를 하나 전으로 옮기게 되면 right보다 한 단계 더 큰 수를 얻을 수 있기 때문에 그 합을 또 기준과 비교할 수 있겠죠?
이렇게 left<right일 동안 반복하면서 조합의 수를 계속 더하고, 기준을 1~$N-2$번째까지 해주면 모든 가능한 triplet의 수를 구할 수 있겠죠? 이때의 복잡도(complexity)는
\[O(N\log N)+(N-2)\times O(N)\approx O(N^2)\]
로써 엄청난 성능 향상이 있었네요 :) 조금 복잡할수도 있으니 앞서 언급한 예제와 함께 고민을 많이 해보시길 :)
이번엔 특별히 C언어를 사용하기로 했습니다 :) 오랜만에 써 보니 많이 까먹었지만, 그래도 재미있네요 :)
#include <stdio.h>
#include <stdlib.h>
/* qsort에 들어갈 compareFn을 정의해줍니다. 내림차순을 위한 것입니다.*/
int wayToSort(const void *i, const void *j){
return *(int*)j - *(int*)i;
}
int numOfTriples(int N, int* L){
/* 내림차순 정렬을 먼저 해줍니다.*/
qsort(L, N, sizeof(int), wayToSort);
int count = 0; //결과값을 0으로 초기화
for(int i=0;i<N-2;i++){ //기준 값을 0에서 N-3까지 가져가면서
int left = i+1; //left의 출발은 기준 값 바로 다음부터
int right = N-1; //right는 가장 작은 막대기부터 시작.
/* left와 right가 만나기 전까지 반복하면서 모든 경우의 수를 다 더해줍니다. */
while(left < right){
if(L[left] + L[right] < L[i]){
count += right-left;
right--;
}
else{
left++;
}
}
}
return count;
}
int main(){
int N = 3;
int L[N] = {4, 2, 10};
printf("%d\n", numOfTriples(N, L));
N = 3;
int L[N] = {1, 2, 3};
printf("%d\n", numOfTriples(N, L));
N = 4;
int L[N] = {5, 2, 9, 6};
printf("%d\n", numOfTriples(N, L));
return 0;
}
결과값:
1
0
2결과값이 잘 나옴을 확인할 수 있네요 :) 조금 복잡할 수도 있지만, 그래도 Sorting을 이용한 trick을 많이 연습하시고 익숙해지시면 어느새 효율적인 알고리즘을 쉽게 찾으시지 않을까 싶습니다! Practice makes perfect!