BOJ 1484 - 다이어트

문제

현재 몸무게의 제곱에서 기억하는 몸무게의 제곱을 뺀 값이 G일 때, 가능한 현재 몸무게를 모두 구하라.

입력

G가 주어진다 (1 <= G <= 100000).

출력

가능한 현재 몸무게를 오름차순으로 출력한다. 없으면 -1을 출력한다.

예제

입력	출력
`15`	`4` `8`

풀이

a^2 - b^2 = (a+b)(a-b) = G를 이용하여 G의 약수 쌍으로 a를 계산한다.

G의 약수 d를 1부터 sqrt(G)까지 탐색한다
a-b = d, a+b = G/d에서 a = (d + G/d) / 2
d와 G/d가 같으면 b=0이므로 제외, 합이 홀수이면 정수가 아니므로 제외
유효한 a를 정렬하여 출력한다

핵심 아이디어: 합차 공식으로 약수 분해하면 O(sqrt(G))에 모든 해를 찾을 수 있다.

코드

import sys
import math
 
input = sys.stdin.readline
 
G = int(input())
 
ans = []
for a in range(1, math.ceil(math.sqrt(G))):
    if G % a == 0:
        b = int(G / a)
 
        if a == b or (a + b) % 2 == 1:
            continue
        ans.append(int((a + b) / 2))
 
if not ans:
    print(-1)
else:
    ans.sort()
    for n in ans:
        print(n)

복잡도

시간: O(sqrt(G))
공간: O(sqrt(G))

문제