[Python] 1711번 직각삼각형

1711번: 직각삼각형 (acmicpc.net)

1711번: 직각삼각형

---

 

22/09/08

 

 

그룹 연습에서 풀다가 실패했던 문제로, 다시 풀어서 맞았습니다! 를 받은 문제이다.

 

단순한 브루트 포스이지만, 맞왜틀을 많이 당한 문제로, 지금 다시 보니 for문과 combinations의 차이점을 느낄 수 있었던 문제였던 것 같다.

---

 

문제 접근 방식:

 

 

단순 무식하게 그냥 세 점을 잡아서, 세 점의 길이 중 가장 긴 변의 제곱이 나머지 두 변의 길이의 제곱의 합과 같은지 확인하는 작업을 걸쳤다.

 

이는 틀린 코드에도 적용되는 사실이였으며, 단지 차이라고는 itertools에서 combinations함수를 사용했냐, 아니면 3중 for문으로 구현했냐의 차이점만 있을 뿐이었다.

 

결론만 이야기하자면, for문으로 구현한 것이 시간 초과를 받지 않았으며, python3로는 절대 통과할 수 없는 문제였었다.

 

이 문제를 python3로 통과하고 싶다면, 다른 아이디어를 사용하여 구현해야 할 것이다.

 

한편, 다른 사람들의 말로는 O(n^3)의 시간 복잡도보다 더 빠른 O(n^2 log n)의 시간 복잡도로 구현할 수 있다고 들었는데, 이는 내가 알아보지 않았고, 이 문제에 그 정도의 시간을 쏟고 싶지 않았기 때문에 다른 방법을 원한다면 다른 블로그 글을 찾아보는 것이 더 좋을 것이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1711번 직각 삼각형
import sys
input = sys.stdin.readline

N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]
avail = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            p1, p2, p3 = points[i], points[j], points[k]
            d1 = (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])
            d2 = (p2[0]-p3[0])*(p2[0]-p3[0]) + (p2[1]-p3[1])*(p2[1]-p3[1])
            d3 = (p3[0]-p1[0])*(p3[0]-p1[0]) + (p3[1]-p1[1])*(p3[1]-p1[1])
            if 2*max(d1,d2,d3) == d1+d2+d3:
                avail += 1
print(avail)