[골드 5] 백준 1484 - 다이어트 (파이썬)

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

풀이

현재 몸무게의 제곱에서과거 몸무게의 제곱을 뺀 값이 G일때 가능한 현재 몸무게를 오름차순으로 출력한다.

결국 b^2 - a^2를 인수분해하면 (b-a)(b + a) = G 이다.

현재 틀린 코드는 다음과 같은 알고리즘을 사용한다.

# 백준 1484 - 다이어트
# 분류 : 수학

G = int(input())

answer = []
for i in range(1, G + 1) :
    if G % i != 0 :
        continue
    
    j = G / i

    # b - a = i

    # b + a = j
    if j <= i :
        continue
    
    # a = (j - i) / 2, b = (j + 1) / 2
    if (j - i) % 2 == 0 and (j + i) % 2 == 0 :
        a = (j - i) // 2
        b = (j + i) // 2
        answer.append(b)

if len(answer) == 0 :
    print(-1)
else :
    answer.sort()
    for i in range(len(answer)) :
        print(answer[i])

1. G 5 i ≠ 0 조건으로 G의 약수를 구한다.
2. J = G i 를 통해 실수형 나눗셈을 진행한다.
3. 자연수 b가 a보다 큰 경우의 모든 쌍을 찾는다.

하지만 이 코드는 틀림~

G = int(input())

a = 1
b = 2
answers = []

while b <= 100000:
    diff = b * b - a * a

a = 1, b = 2 부터 시작하며, b^2 - a^2를 구해서 G와 비교한다.

if diff == G:
    answers.append(b)
    b += 1
elif diff < G:
    b += 1

현재 몸무게 b가 정답 조건을 만족하면 리스트에 추가한다.

다른 경우는 b를 더 키워서 ㅈb^2 - a^2의 값으로 키운다.

if answers:
    for ans in answers:
        print(ans)
else:
    print(-1)

정답이 있으면 오름차순으로 출력하고, 없으면 -1을 출력한다

시간 복잡도 분석

• b는 최대 10^5까지만 돌기 때문에 시간 제한 안에 충분히 처리 할 수 있다,

코드

# 백준 1484 - 다이어트
# 분류 : 수학 / 투 포인터

G = int(input())

a = 1
b = 2
answers = []

while b <= 100000:  # 100,000^2 - 1^2 = 충분히 커짐
    diff = b * b - a * a

    if diff == G:
        answers.append(b)
        b += 1
    elif diff < G:
        b += 1
    else:
        a += 1

if answers:
    for ans in answers:
        print(ans)
else:
    print(-1)