[Python] 4563번 리벤지 오브 피타고라스

https://www.acmicpc.net/problem/4563

4563번: 리벤지 오브 피타고라스

---

 

23/09/07

 

 

정수론적 지식을 요구하는 문제로, 주어진 수의 범위에 대해서 어떻게 효율적인 시간으로 판별할 수 있을지 생각해야되는 문제이다.

---

 

문제 접근 방식:

 

 

당연히 문제에서 요구하는 바를 나이브하게 접근하면 주어지는 수의 범위가 매우 크기 때문에 시간초과를 받을 가능성이 매우 크다.

 

문제에서 요구하는 바를 다시 상기시켜보자.

 

$A < B$이고, $A$의 값이 최대 $2^{20}$까지 주어질 때, $A^2 + B^2 = C^2$(단, $C$는 정수)를 만족하는 $B$의 값을 찾는 것이 우리의 목표이다.

 

처음 접근한 방법은 $A < B$의 제약조건에 따라, $B$를 살펴볼 때, $A+1$부터 저 조건을 만족시키는지 확인하는 방법이었다.

 

그러다가 만약 삼각형의 조건에 벗어나거나 $C$가 빗변이 되지 않는 경우라면 종료를 했다.

 

당연히 시간초과가 났고, 조금 기발한 방법을 강구해야만 했다.

 

문제 조건을 살펴보았고, $A$의 최대 범위가 꽤 크다는 것을 유의 깊게 살펴보았다.

 

시간 안에 들어올 수 있는 시간복잡도는 $O(N)$이나 그 밑의 시간복잡도로 정리가 됨을 짐작했다.

 

 

피타고라스의 정리 식을 $A$에 대해 정리해 보면 다음과 같은 식을 얻을 수 있다.

 

$$A^2 = C^2 - B^2 = (C-B)(C+B)$$

 

즉, 합차 공식으로 인수분해가 됨을 알 수 있다.

 

여기서 $C-B = K$라고 한다면, $K$는 $C+B$보다 작기 때문에, $K$의 최대 범위는 $A$보다 하나 적은 숫자까지 밖에 안됨을 알 수 있었다.

 

즉, $1$부터 시작해서 $A$이전까지 $K$를 살펴보며, 저 조건을 만족하는지 따져주면 된다.

 

$K$와 $A$에 대해서 우리가 구하고자 하는 $B$의 식을 정리하면, 다음과 같이 나옴을 알 수 있다.

 

$$(A^2/K -K)/2 = B$$

 

물론 여기서 $K$는 $A$의 약수이다.

 

이 식을 통해 $B$값을 구하고, 이 $B$값이 $A$값보다 크다면 조건을 만족하는 것이므로 개수를 $+1$, 아니라면 종료하도록 해주었다.

 

---

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

# 4563번 리벤지 오브 피타고라스
# 수학
'''
접근 방법:
a*a = (c-b)(c+b)
a*a를 나누는 k = c-b가 있다고 하자
k는 a까지의 범위를 가짐
(a*a//k - k)//2 = b
'''
def solve(a):
    cnt = 0
    for k in range(1, a):
        if (a*a) % k == 0 and ((a*a)//k - k) % 2 == 0:
            b = ((a*a)//k - k)//2
            if b <= a:
                break
            cnt += 1
    return cnt
def main():
    while True:
        a = int(input())
        if a == 0:
            return
        print(solve(a))

main()