목차

직각삼각형
- 풀이
- 코드
토론

직각삼각형

ps
링크	acmicpc.net/…
출처	BOJ
문제 번호	1711
문제명	직각삼각형
레벨	골드 5
분류	기하학
시간복잡도	O(n^2logm)
인풋사이즈	n<=1,500, m<=10*9
사용한 언어	Python 3.13
제출기록	35560KB / 2184ms
최고기록	1660ms
해결날짜	2025/02/18

풀이

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

코드

Dependency: teflib.combinatorics.linear_homogeneous_recurrence

BOJ, 골드 3, linear homogeneous recurrence