[BOJ] 백준 28683 피타!피타!피타츄! Python

import sys
import math
input = sys.stdin.readline
N = int(input())

if int(math.sqrt(N)) - math.sqrt(N) == 0:
    print(-1)
else:
    cnt1 = 0
    #N이 빗변인 경우
    for i in range (1,int(math.sqrt(N/2))+1):
        j = N - i**2
        #j가 어떤 정수의 제곱꼴인지 판단하는 방법#
        if math.sqrt(j) - int(math.sqrt(j)) == 0:
            cnt1 += 1
        else:
            continue
    #N이 빗변이 아닐 경우
    #N = B ** 2 - A ** 2 = (B+A)(B-A)로 계산된다. 두 수의 기우성이 동일해야함.
    cnt2 = 0
    for i in range (1,int(math.sqrt(N))+1):
        if N % i == 0:
            if (i + (N // i)) % 2 == 0:
                if i == N // i:
                    continue
                else:
                    cnt2 += 1
        else:
            continue

    print(cnt1 + cnt2)

얼마전 고대 프로그래밍 기출 문제.

먼저, 이러한 순서쌍이 무한히 존재하는 경우는 쉽게 찾을 수 있는데,
주어진 N이 제곱수인 경우에 순서쌍이 무한히 존재하는 것을 용이하게 확인할 수 있다.

(예를 들어서, N = 4인 경우에는 한변의 길이가 2이고, 나머지 두 변중 하나의 길이가 정수이기만 하면되므로, 무한히 만들 수 있다. 왜냐하면 길이 2인 변을 빗변이 아닌 변으로서 생각하면 OK)

한편, N이 제곱수가 아닌 경우에는 케이스를 나눠보아야한다.

Case 1. N이 어떤 두 제곱수의 합으로 이루어져있는지 확인 (즉, 루트 N이 빗변인 경우)

Case 2. 루트 N이 빗변이 아닌 경우. 이때, 우리는 나머지 두 변이 "반드시" 정수가 되어야하는 부분에 주목할 수 있다.
즉, N = B^2 - A^2 = (B + A)(B - A) 로 둘 수 있다.
(여기서 B는 빗변의 길이, A는 남은 변의 길이)

 

여기서 한가지 수학적인 성질이 더 쓰이게 되는데 바로 '기우성'이다.
B + A, B - A는 같은 기우성을 지니고 있다. 둘 중 한쪽이 홀수라면 나머지 한쪽도 반드시 홀수여야하고, 한쪽이 짝수라면 나머지 한쪽도 짝수이어야한다.

그리고, A는 0이 아니므로 B + A > B - A가 성립하는 것을 알 수 있다.

여기서 뭔가 보이는가? 그렇다. 바로 약수찾기 문제에 귀결하게 된다.
즉, N = 96으로 예를 들어보면 96 = 96 x 1 = 48 x 2 = 32 x 3 = 24 x 4 = 16 x 6 = 12 x 8
이런 식으로 나타낼 수 있다.
이때 B+A = 48, B-A = 2 < OK
B+A = 32, B-A = 3 < FAIL (왜냐하면 두 수의 홀짝성이 다르기때문)
B+A = 24, B-A = 4 < OK
B+A = 16, B-A = 6 < OK
B+A = 12, B-A = 8 < OK

이렇게 되는 것을 확인할 수 있겠다 !

마지막으로 Case1의 카운트 수와 Case2의 카운트 수를 서로서로 더해준다면 끝 ! (갯수가 유한한 경우)