[Python] 백준 28683: 피타! 피타! 피타츄! (3단계로 자세하게 접근)

문제 링크

28683번: 피타! 피타! 피타츄!

문제 요약

삼각형 한 변 길이의 제곱인 n이 주어진다. sqrt(n) 길이의 변을 가지는 가능한 합동이 아닌 서로 다른 직각삼각형의 갯수를 출력하라.
단, 직각삼각형의 최소한 두 변은 정수여야 한다. 가능한 직각삼각형의 갯수가 셀 수 없이 많다면 -1를 출력한다.
(피타! 피타! 피타츄!의 의미를 글을 쓰면서 깨달았다 😅) 

풀이 설명

꽤 여러번의 시도와 다른 사람들의 풀이를 참고한 끝에 문제를 풀었다.

여러 번의 시도들

첫 번째 시도:  경우의 수를 나누어 접근 (if n==제곱수) (시간 초과)

기존에는 n이 제곱수거나 아니거나의 두 가지 경우로 나누어 생각해보았다.

n이 제곱수라면, 다른 한 변의 길이를 임의의 제곱수로 하고, 나머지는 적절한 길이로 두면 쉽게 두 개 변의 길이가 정수인 직각삼각형이 성립되어 직각삼각형의 갯수는 무한히 많아진다. 따라서, 제곱수인 경우 -1을 출력한다.

n_sqrt=math.sqrt(n)
if n_sqrt%1==0:
    triangle_num=-1

if triangle_num==-1:
    print(-1)
    exit()

 

제곱수가 아닌 경우, n이 직각삼각형의 한 변의 제곱이 되려면 아래와 같이 피타고라스 정리를 만족하여야 한다. (A와 B는 직각삼각형 나머지 한 변들)

n이 직각삼각형의 한 변이 되기 위해서 피타고라스 정리를 만족하여야 한다.

double_list=[]
prev=0
for i in range(1, 1000001):
    if i*i-prev>n:
        break
    double_list.append(i*i)
    prev=i*i

l=len(double_list)
for i in range(l):
    for j in range(i,l):
        if double_list[i]+n<double_list[j]:
            break
        elif double_list[i]+double_list[j]==n:
            triangle_num+=1
            break
        elif double_list[i]+n==double_list[j]:
            triangle_num+=1
            break

B 제곱 - A 제곱이 n보다 크지 않은 경우로 한정하여, 모든 제곱수들을 저장한다. 그리고 제곱수 2개를 선택하는 모든 경우를 순환하면서 위의 조건에 만족하는 경우 가능한 삼각형 갯수(triangle_num)에 1씩 더해준다.

 

이 문제는 시간 제한이 1초였고, 정수의 입력 제한이 1<=n<=10^12 였기 때문에, 1초 동안 가능한 연산 횟수인 1억(10^8) 번을 고려한다면 당연히 시간 초과가 날 수밖에 없었다. 그리고 역시 시간 초과났다. 😅 

두 번째 시도: 다른 분들 풀이 참고 (틀렸습니다.)

다른 분의 풀이를 참고하다, 놓쳤던 사실을 깨달았다.

백준 28683 피타!피타!피타츄! (python,pypy)

n이 빗변의 제곱이 아닌 경우, 곱셈 공식을 사용하여서 이 문제를 약수 찾기 문제로 치환할 수 있다는 것이었다.

더불어 B-A와 B+A가 하나가 짝수면 나머지도 짝수, 하나가 홀수면 나머지도 홀수이기 때문에 이 조건을 확인하여 가능한 직각삼각형의 갯수를 구할 수 있었다.

 

거의 다 온 상황에서, 범위에 대한 고려 없이 코드를 짜니 직각삼각형을 중복해서 카운트하여, 오답 처리되었다.

세 번째 시도: 탐색 범위 축소 (맞았습니다!!)

for i in range(1, 1000001):
    if i*i>n//2:
        break
    double_list.append(i*i)
    prev=i*i

def check_double(num):
    num_sqrt=math.sqrt(num)
    if num_sqrt%1==float(0):
        return True
    if num_sqrt%1!=float(0):
        return False

l=len(double_list)
for i in range(l):
    if check_double(n-double_list[i]):
        triangle_num+=1

for i in range(1, int(math.sqrt(n))+1):
    if n%i==0:
        if (n//i)%2==0 and i%2==0:
            triangle_num+=1
        elif (n//i)%2==1 and i%2==1:
            triangle_num+=1

 

1번 경우를 탐색할 제곱수 배열의 경우, n//2보다 크면 위 코드에서 중복하여 직각삼각형을 카운트할 수 있기 때문에 n//2를 준으로 범위를 한정한다.

2번 경우를 탐색할 때, 기존에는 range(1, n)으로 무지성 탐색을 했었는데 sqrt(n)까지 탐색한 후에는 이미 찾은 직각삼각형의 긴 변을 탐색하는 꼴이어서 range(1, int(math.sqrt(n))+1)로 범위를 한정한다.

 

2번 아이디어 진짜 참신하고 좋다.어려운 개념은 아니지만,
다른 문제 중에도 수학의 관점에서 더 쉽게 풀 수 있는 문제가 있을 것 같다고 생각한다!