백준 1484 [다이어트] 파이썬

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

1484번: 다이어트

#백준 1484

G=int(input())

a=1
b=2
ans=[]
while (a+b)<=G:
    a=1
    while a<b:
        if ((b+a)*(b-a))==G:
            ans.append(b)
        a+=1
    b+=1

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

O (N^2) 의 시간복잡도로 문제를 풀었다. pypy3로 돌려서 성공했는데, 역시나.... 문제가 요구하는건 이게 아니었다.

 

if __name__== '__main__':
    G = int(input())
    P = [x for x in range(1, 100001)]
    Q = [x for x in range(1, 100001)]
    N, M = 100000, 100000
    left, right = 0, 0 # 투 포인터
    ans = []
    while left < N and right < M:
        # G는 현재 몸무게(A)의 제곱 - 성원이가 기억하고 있던 몸무게(B)의 제곱
        # G = A^2 - B^2 => (A + B)*(A - B)
        tmp = (P[left] + Q[right]) * (P[left] - Q[right])
        if tmp == G: ans.append(P[left])
        if tmp < G:
            left += 1
            continue
        right += 1
    if not ans: print(-1)
    else:
        for y in ans: print(y)

이 분이 푸신 것처럼 투포인터를 이용하면, O(N)의 시간복잡도로 문제를 해결할 수 있다.

https://baby-ohgu.tistory.com/19

[백준 1484] 다이어트 (Python)

 

 

좀 더 깊이 생각해보자..