[BOJ][🟡5][백준#01484] 다이어트

문제 출처

BAEKJOON Online Judge #1484

문제

성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. 성원이는 엔토피아가 선물해준 저울 위에 올라갔다. “안돼!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! G 킬로그램이나 더 쪘어ㅜㅠ”라고 성원이가 말했다. 여기서 말하는 G킬로그램은 성원이의 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다. 성원이의 현재 몸무게로 가능한 것을 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 G가 주어진다. G는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우는 제외해야 한다.

예제

입력

15

출력

4
8

My Sol

def main():
    G = int(input())
    ret = []
    for n in range(1, int(G**(1/2))+1):
        if G%n: continue
        n1, n2 = n, G//n
        if not (n1 and n2): continue
        if (n1==n2) or (n1+n2)%2: continue
        ret.append((n1+n2)//2)

    return ret[::-1] if ret else [-1]

print(*main(), sep='\n')

문제의 풀이보다 문제 자체를 이해하는 데에 더 시간이 들었던 문제였다. a**2 - b**2 = (a+b)*(a-b) 라는 식을 기본적으로 알고 있어야 한다.

1. 우선 (현재 몸무게**2 - 예전 몸무게**2)를 의미하는 G를 입력으로 받는다. 이 G라는 수가 두 자연수의 곱으로 표현될 수 있다면 이로부터 현재 몸무게를 유추할 수 있다.
2. 두 자연수의 곱으로 표현된다면, 이 두 자연수를 a, b라고 할 때, 두 수는 모두 G 의 약수가 된다. 때문에 에라토스테네스의 체 공식을 활용한다. 1부터 G의 제곱근까지의 모든 자연수에 대해 G에 나누어보았을 때, 나누어떨어지면 해당하는 수와 그 나누어진 몫이 모두 약수인 것이다.
3. 그렇다면 이를 n1과 n2로 지정하고 현실적으로 배제하는 조건을 둔다. 예를 들면, 두 수는 각각 현재와 과거의 몸무게를 의미하므로 둘 다 0이 되면 안 된다. 그리고 몸무게는 더 추가되었다고 했으므로 n1과 n2는 같으면 안된다.
4. 이를 만족한다면 (현재 몸무게 + 과거몸무게)*(현재 몸무게 - 과거몸무게)가 곧 G가 될텐데, 이것이 각각 n2와 n1이 될 것이다. 그렇다면 현재 몸무게는 두 수의 합을 2로 나눈 (n1+n2)//2이 될 것이다. 이것이 자연수여야 하므로 합이 홀수라면 역시 배제해준다.
5. 모든 과정을 통과한 수가 현재 몸무게의 후보가 되는데, 반복문을 진행할수록 n과 G//n의 간극은 좁혀지므로 먼저 발견되는 몸무게 후보일수록 더 크다. 때문에 모든 후보들을 모은 ret 배열을 뒤집어 반환한다. 만약 후보가 없어 ret이 없다면 -1을 출력하기 위해 [-1]을 반환한다.
6. main 함수 밖에서 이를 한 줄씩 출력한다.

결과

맞았습니다!!