테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 직각삼각형 ======

===== 풀이 =====
  * [[ps:problems:boj:3008]] 과 동일한 문제이다. 풀이는 그쪽을 참고.
  * 문제의 입력 범위까지 [[ps:problems:boj:3008]]와 동일한데 이쪽이 티어가 낮은것은, 제한시간이 5초로 길기 때문이다. 이로 인해서 O(n^3) 알고리즘이 빡빡하게 돌아간다고 한다.
    * 세점을 고르는 모든 경우에 대해서 삼각형을 이루는지를 확인하는 브루트포스 알고리즘을 사용한다면, C(n,3)번의 체크가 필요하다. 이게 대략 5.6억번이라서 시간내에 통과한다고 한다. 파이썬의 경우도 pypy를 사용하고 상수최적화를 잘 하면 통과된다고 함.


===== 코드 =====
<dkpr py>

</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#linear_homogeneous_recurrence|teflib.combinatorics.linear_homogeneous_recurrence]]

{{tag>BOJ ps:problems:boj:골드_3 ps:teflib:linear_homogeneous_recurrence}}