문제 해결 전략
- n개 중에서 3개를 뽑는건데, 조건으로는 3개의 친구가 모두 친구 관계여야 한다.
-
조건을 빼고 n개 중에서 3개를 뽑으면 4000의 3승이므로 시간초과다.
-
-> 다른 방법을 생각해야 함.
-
3명의 관계가 모두 친구 관계라는 점을 이용해서 접근해야 한다.
-
a와 b가 친구 관계인 상태에서 b와 c가 친구 관계인지 라는 조건을 가지고 진행해야 한다.
-
이렇게 되면 시간복잡도는 n제곱 + nm 이 된다.
nm은 왜냐하면 모든 친구 관계의 수 m과 for문 돌리는 n개이기 때문이다.
🔥🔥🔥