ps:problems:boj:1711
직각삼각형
| 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를 사용하고 상수최적화를 잘 하면 통과된다고 함.
코드
ps/problems/boj/1711.txt · 마지막으로 수정됨: 2025/02/18 14:19 저자 teferi
토론