사용자 도구

사이트 도구


ps:problems:boj:3000

직각 삼각형

ps
링크acmicpc.net/…
출처BOJ
문제 번호3000
문제명직각 삼각형
레벨실버 1
분류

기하학

시간복잡도O(n)
인풋사이즈n<=100,000
사용한 언어Python 3.13
제출기록53760KB / 172ms
최고기록100ms
해결날짜2025/02/18

풀이

  • 직각 삼각형의 개수 와 비슷해보이지만, 축에 평행한 직각삼각형만 세면 된다는 조건이 들어가기 때문에 훨씬 간단하다.
  • 한 점을 고정했을때, 그 점과 x값이 같은 점 한개와 y값이 같은 점 한개를 찾으면 그 점을 직각인 꼭짓점으로 갖는 직각삼각형을 찾을 수 있다.
  • 결국, 점 P를 직각인 꼭짓점으로 갖는 직각삼각형의 개수는, {P와 x좌표가 같은 점의 개수} * {P와 y좌표가 같은 점의 개수}로 계산할수 있다. x좌표 값마다 점의 개수를 세어놓은 딕셔너리와, y좌표 값마다 점의 개수를 세어놓은 딕셔너리를 미리 O(N)에 만들어 놓는다면, 특정 점을 직각인 꼭짓점으로 갖는 직각삼각형의 개수를 O(1)에 계산 가능하다. 이것을 N개의 점에 대해서 모두 구하면 O(N)이 걸린다.

코드

"""Solution code for "BOJ 3000. 직각 삼각형".

- Problem link: https://www.acmicpc.net/problem/3000
- Solution link: http://www.teferi.net/ps/problems/boj/3000

Tags: [geometry]
"""

import collections
import sys


def main():
    N = int(sys.stdin.readline())
    X_and_Y = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    x_counter = collections.Counter(x for x, y in X_and_Y)
    y_counter = collections.Counter(y for x, y in X_and_Y)
    answer = sum(
        (x_counter[x_i] - 1) * (y_counter[y_i] - 1) for x_i, y_i in X_and_Y
    )

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
P H B F A
 
ps/problems/boj/3000.txt · 마지막으로 수정됨: 2025/02/18 15:18 저자 teferi